New results on rectilinear crossing numbers and plane embeddings

We show that if a graph has maximum degree d and crossing number k, its rectilinear crossing number is at most O(dk²). Hence for graphs of bounded degree, the crossing number and the rectilinear crossing number are bounded as functions of one another. We also obtain a generalization of Tutte's theorem on convex embeddings of 3-connected plane graphs. © 1929 John Wiley & Sons, Inc.     

On k-planar crossing numbers

The k-planar crossing number of a graph is the minimum number of crossings of its edges over all possible drawings of the graph in k planes. We propose algorithms and methods for k-planar drawings of general graphs together with lower bound techniques. We give exact results for the k-planar crossing number of K_2k+1,q, for k?2. We prove tight bounds for complete graphs. We also study the rectilinear k-planar crossing number.     

Visibility Drawings of Plane 3-Trees with Minimum Area

A visibility drawing of a plane graph G is a drawing of G where each vertex is drawn as a horizontal line segment and each edge is drawn as a vertical line segment such that the line segments use only grid points as their endpoints. The area of a visibility drawing is the area of the smallest rectangle on the grid which encloses the drawing. A minimum-area visibility drawing of a plane graph G is a visibility drawing of G where the area is the minimum among all possible visibility drawings of G. The area minimization for grid visibility representation of planar graphs is NP-hard. However, the problem can be solved for a fixed planar embedding of a hierarchically planar graph in quadratic time. In this paper, we give a polynomial-time algorithm to obtain minimum-area visibility drawings of plane 3-trees.     

On the Pseudolinear Crossing Number

A drawing of a graph is pseudolinear if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The pseudolinear crossing number of a graph G is the minimum number of pairwise crossings of edges in a pseudolinear drawing of G. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph.     

Odd Crossing Number and Crossing Number Are Not the Same

The crossing number of a graph is the minimum number of edge intersections in a plane drawing of a graph, where each intersection is counted separately. If instead we count the number of pairs of edges that intersect an odd number of times, we obtain the odd crossing number. We show that there is a graph for which these two concepts differ, answering a well-known open question on crossing numbers. To derive the result we study drawings of maps (graphs with rotation systems).     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

Proper 1-immersions of graphs triangulating the plane

In this paper we study what planar graphs are “rigid” enough such that they can not be drawn on the plane with few (1, 2, or 3) crossings per edge. A graph drawn on the plane is k$k$-immersed in the plane if each edge is crossed by at most k$k$ other edges. By a proper  k$k$-immersion of a graph we mean a k$k$-immersion of the graph in the plane such that there is at least one crossing point. We give a characterization (in terms of forbidden subgraphs) of 4-connected graphs which triangulate the plane and have a proper 1-immersion. We show that every planar graph has a proper 3-immersion.     

Nearly light cycles in embedded graphs and crossing‐critical graphs

We find a lower bound for the proportion of face boundaries of an embedded graph that are nearly light (that is, they have bounded length and at most one vertex of large degree). As an application, we show that every sufficiently large k‐crossing‐critical graph has crossing number at most 2k + 23. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 151–156, 2006     

Which Crossing Number Is It Anyway?

A drawing of a graph G is a mapping which assigns to each vertex a point of the plane and to each edge a simple continuous arc connecting the corresponding two points. The crossing number of G is the minimum number of crossing points in any drawing of G. We define two new parameters, as follows. The pairwise crossing number (resp. the odd-crossing number) of G is the minimum number of pairs of edges that cross (resp. cross an odd number of times) over all drawings of G. We prove that the largest of these numbers (the crossing number) cannot exceed, twice the square of the smallest (the odd-crossing number). Our proof is based on the following generalization of an old result of Hanani, which is of independent interest. Let G be a graph and let E₀ be a subset of its edges such that there is a drawing of G, in which every edge belonging to E₀ crosses any other edge an even number of times. Then g can be redrawn so that the elements of E₀ are not involved in any crossing. Finally, we show that the determination of each of these parameters is an NP-hard problem and it is NP-complete in the case of the crossing number and the odd-crossing number.     

Approximating the fixed linear crossing number

We present a randomized polynomial-time approximation algorithm for the fixed linear crossing number problem (FLCNP). In this problem, the vertices of a graph are placed in a fixed order along a horizontal “node line” in the plane, each edge is drawn as an arc in one of the two half-planes (pages), and the objective is to minimize the number of edge crossings. FLCNP is NP-hard, and no previous polynomial-time approximation algorithms are known. We show that the problem can be generalized to k pages and transformed to the maximum k-cut problem which admits a randomized polynomial-time approximation. For the 2-page case, our approach leads to a randomized polynomial time 0.878+0.122ρ approximation algorithm for FLCNP, where ρ is the ratio of the number of conflicting pairs (pairs of edges that cross if drawn in the same page) to the crossing number. We further investigate this performance ratio on the random graph family G_n,1/2, where each edge of the complete graph K_n occurs with probability . We show that a longstanding conjecture for the crossing number of K_n implies that with probability at least 1-4e^-λ2, the expected performance bound of the algorithm on a random graph from G_n,1/2 is 1.366+O(λ/n). A series of experiments is performed to compare the algorithm against two other leading heuristics on a set of test graphs. The results indicate that the randomized algorithm yields near-optimal solutions and outperforms the other heuristics overall.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

Super Restricted Edge Connectivity of Regular Graphs

An edge cut of a connected graph is called restricted if it separates this graph into components each having order at least 2; a graph G is super restricted edge connected if G−S contains an isolated edge for every minimum restricted edge cut S of G. It is proved in this paper that k-regular connected graph G is super restricted edge connected if k > |V(G)|/2+1. The lower bound on k is exemplified to be sharp to some extent. With this observation, we determined the number of edge cuts of size at most 2k−2 of these graphs. Supported by NNSF of China (10271105); Ministry of Science and Technology of Fujian (2003J036); Education Ministry of Fujian (JA03147)     

Graphs drawn with few crossings per edge

We show that if a graph ofv vertices can be drawn in the plane so that every edge crosses at mostk>0 others, then its number of edges cannot exceed 4.108kv. Fork4, we establish a better bound, (k+3)(v–2), which is tight fork=1 and 2. We apply these estimates to improve a result of Ajtai et al. and Leighton, providing a general lower bound for the crossing number of a graph in terms of its number of vertices and edges.Supported by NSF grant CCR-94-24398 and PSC-CUNY Research Award 667339.Supported by OTKA-T-020914, OTKA-F-22234 and the Margaret and Herman Sokol Postdoctoral Fellowship Award.     

Algorithms for coloring semi-random graphs

The graph coloring problem is to color a given graph with the minimum number of colors. This problem is known to be NP-hard even if we are only aiming at approximate solutions. On the other hand, the best known approximation algorithms require n^δ (δ>0) colors even for bounded chromatic (k-colorable for fixed k) n-vertex graphs. The situation changes dramatically if we look at the average performance of an algorithm rather than its worst case performance. A k-colorable graph drawn from certain classes of distributions can be k-colored almost surely in polynomial time. It is also possible to k-color such random graphs in polynomial average time. In this paper, we present polynomial time algorithms for k-coloring graphs drawn from the semirandom model. In this model, the graph is supplied by an adversary each of whose decisions regarding inclusion of edges is reversed with some probability p. In terms of randomness, this model lies between the worst case model and the usual random model where each edge is chosen with equal probability. We present polynomial time algorithms of two different types. The first type of algorithms always run in polynomial time and succeed almost surely. Blum and Spencer [J. Algorithms, 19 , 204–234 (1995)] have also obtained independently such algorithms, but our results are based on different proof techniques which are interesting in their own right. The second type of algorithms always succeed and have polynomial running time on the average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work for semirandom graphs drawn from a wide range of distributions and work as long as p≥n^−α(k)+ϵ where α(k)=(2k)/((k−1)(k+2)) and ϵ is a positive constant. © 1998 John Wiley & Sons, Inc. Random Struct. Alg., 13, 125–158 (1998)     

Game chromatic index of k‐degenerate graphs

We consider the following edge coloring game on a graph G. Given t distinct colors, two players Alice and Bob, with Alice moving first, alternately select an uncolored edge e of G and assign it a color different from the colors of edges adjacent to e. Bob wins if, at any stage of the game, there is an uncolored edge adjacent to colored edges in all t colors; otherwise Alice wins. Note that when Alice wins, all edges of G are properly colored. The game chromatic index of a graph G is the minimum number of colors for which Alice has a winning strategy. In this paper, we study the edge coloring game on k‐degenerate graphs. We prove that the game chromatic index of a k‐degenerate graph is at most Δ + 3k − 1, where Δ is the maximum vertex degree of the graph. We also show that the game chromatic index of a forest of maximum degree 3 is at most 4 when the forest contains an odd number of edges. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 144–155, 2001     

Odd 4‐edge‐colorability of graphs

An odd k‐edge‐coloring of a graph G is a (not necessarily proper) edge‐coloring with at most k colors such that each nonempty color class induces a graph in which every vertex is of odd degree. Pyber (1991) showed that every simple graph is odd 4‐edge‐colorable, and Lužar et al. (2015) showed that connected loopless graphs are odd 5‐edge‐colorable, with one particular exception that is odd 6‐edge‐colorable. In this article, we prove that connected loopless graphs are odd 4‐edge‐colorable, with two particular exceptions that are respectively odd 5‐ and odd 6‐edge‐colorable. Moreover, a color class can be reduced to a size at most 2.     

An analysis of some linear graph layout heuristics

The worst-case performances of some heuristics for the fixed linear crossing number problem (FLCNP) are analyzed. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal “node line” in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In FLCNP, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems Masuda et al., 1990. In this paper we show that for each of the heuristics described, there exist classes of n-vertex, m-edge graphs which force it to obtain a number of crossings which is a function of n or m when the optimal number is a small constant. This leaves open the problem of finding a heuristic with a constant error bound for the problem.     

On rectilinear duals for vertex-weighted plane graphs

Let G=(V,E) be a plane triangulated graph where each vertex is assigned a positive weight. A rectilinear dual of G is a partition of a rectangle into |V| simple rectilinear regions, one for each vertex, such that two regions are adjacent if and only if the corresponding vertices are connected by an edge in E. A rectilinear dual is called a cartogram if the area of each region is equal to the weight of the corresponding vertex. We show that every vertex-weighted plane triangulated graph G admits a cartogram of constant complexity, that is, a cartogram where the number of vertices of each region is constant. Furthermore, such a rectilinear cartogram can be constructed in O(nlogn) time where n=|V|.     

Interval Routing onk-Trees

A graph has an optimall-interval routing scheme if it is possible to direct messages along shortest paths by labeling each edge with at mostlpairwise-disjoint subintervals of the cyclic interval [1…n] (where each node of the graph is labeled by an integer in the range). Although much progress has been made forl = 1, there is as yet no general tight characterization of the classes of graphs associated with largerl. Bodlaenderet al. have shown that under the assumption of dynamic cost links, each graph with an optimall-interval routing scheme has treewidth of at most 4l. For the setting without dynamic cost links, this paper addresses the complementary question of the number of intervals required to label classes of graphs of treewidthk. Although it has been shown that there exist graphs of treewidth 2 that require a nonconstant number of intervals, our work demonstrates a class of graphs of treewidth 2, namely 2-trees, that are guaranteed to allow 3-interval routing schemes. In contrast, this paper presents a 2-tree that cannot have a 2-interval routing scheme. For generalk, anyk-tree is shown to have an optimal interval routing scheme using 2^{k + 1}intervals per edge.     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation