We prove crossing number inequalities for geometric graphs whose vertex sets are taken from a d-dimensional grid of volume N and give applications of these inequalities to counting the number of non-crossing geometric graphs that can be drawn on such grids. In particular, we show that any geometric graph with m >= 8N edges and with vertices on a 3D integer grid of volume N, has ((m^2 n) (m n)) crossings. In d-dimensions, with d >= 4, this bound becomes (m^2 n). We provide matching upper bounds for all d. Finally, for d >= 4 the upper bound implies that the maximum number of crossing-free geometric graphs with vertices on some d-dimensional grid of volume N is n^ (n). In 3 dimensions it remains open to improve the trivial bounds, namely, the 2^ (n) lower bound and the n^O(n) upper bound.
Finally, we note that Bukh and Hubard @cite_9 have defined a form of crossing number for 3-dimensional geometric graphs that are not necessarily grid graphs. In their definition, a 4-tuple of vertex-disjoint edges form a if there is a line that intersects every edge in the 4-tuple. The , @math , of a 3-d geometric graph, @math , is the number of space crossings formed by @math 's edges. They show that a 3-d geometric graph @math with @math vertices and @math edges has a space crossing number @math . An easy lifting argument shows that this bound on the space crossing number almost implies the Crossing Lemma; specifically, it shows that the number of crossings in a graph with @math vertices and @math edges drawn in the plane is @math .
@cite_9
2028446993 2507315201 2338992247 2080201242
It was proved by [M.R. Garey, D.S. Johnson, Crossing number is NP-complete, SIAM J. Algebraic Discrete Methods 4 (1983) 312-316] that computing the crossing number of a graph is an NP-hard problem. Their reduction, however, used parallel edges and vertices of very high degrees. We prove here that it is NP-hard to determine the crossing number of a simple 3-connected cubic graph. In particular, this implies that the minor-monotone version of the crossing number problem is also NP-hard, which has been open till now. It is very well-known that there are precisely two minimal non-planar graphs: K 5 and K 3 , 3 (degree 2 vertices being irrelevant in this context). In the language of crossing numbers, these are the only 1-crossing-critical graphs: they each have crossing number at least one, and every proper subgraph has crossing number less than one. In 1987, Kochol exhibited an infinite family of 3-connected, simple, 2-crossing-critical graphs. In this work, we: (i) determine all the 3-connected 2-crossing-critical graphs that contain a subdivision of the Mobius Ladder V 10 ; (ii) show how to obtain all the not 3-connected 2-crossing-critical graphs from the 3-connected ones; (iii) show that there are only finitely many 3-connected 2-crossing-critical graphs not containing a subdivision of V 10 ; and (iv) determine all the 3-connected 2-crossing-critical graphs that do not contain a subdivision of V 8 . We define a variant of the crossing number for an embedding of a graph G into â3, and prove a lower bound on it which almost implies the classical crossing lemma. We also give sharp bounds on the rectilinear space crossing numbers of pseudo-random graphs. Being motivated by John Tantalo's Planarity Game, we consider straight line plane drawings of a planar graph G with edge crossings and wonder how obfuscated such drawings can be. We define obf(G), the obfuscation complexity of G, to be the maximum number of edge crossings in a drawing of G. Relating obf(G) to the distribution of vertex degrees in G, we show an efficient way of constructing a drawing of G with at least obf(G) 3 edge crossings. We prove bounds (@d(G)^2 24-o(1))n^2@?obf(G) =2. The shift complexity of G, denoted by shift(G), is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of G (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If @d(G)>=3, then shift(G) is linear in the number of vertices due to the known fact that the matching number of G is linear. However, in the case @d(G)>=2 we notice that shift(G) can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing D of a planar graph, it is NP-hard to find an optimum sequence of shifts making D crossing-free.