 Crossing number (graph theory)

In graph theory, the crossing number cr(G) of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.
The concept originated in Turán's brick factory problem, in which Pál Turán asked to determine the crossing number of the complete bipartite graph K_{m,n}.^{[1]}
Contents
History
Zarankiewicz attempted to solve Turán's brick factory problem;^{[2]} his proof contained an error, but he established a valid upper bound of
for the crossing number of a complete bipartite graph K_{m,n}. The conjecture that this inequality is actually an equality is now known as Zarankiewicz' Crossing Number Conjecture.
The problem of determining the crossing number of the complete graph was first posed by Anthony Hill, and appears in print in 1960.^{[3]} Hill and his collaborator John Ernest were two constructionist artists fascinated by mathematics who not only formulated this problem but also originated a conjectural upper bound for this crossing number, which Richard Guy published in 1960.^{[3]} As of March 2009, both problems remain unresolved except for a few special cases; there has been some progress on lower bounds, as reported by de Klerk et al. (2006).^{[4]}
The Albertson conjecture, formulated by Michael O. Albertson in 2007, states that, among all graphs with chromatic number n, the complete graph K_{n} has the minimum number of crossings. That is, if Guy's conjecture on the crossing number of the complete graph is valid, every nchromatic graph has crossing number at least equal to the formula in the conjecture. It is now known to hold for n ≤ 16.^{[5]}
Variations
Without further qualification, the crossing number allows drawings in which the edges may be represented by arbitrary curves; the rectilinear crossing number requires all edges to be straight line segments, and may differ from the crossing number. In particular, the rectilinear crossing number of a complete graph is essentially the same as the minimum number of convex quadrilaterals determined by a set of n points in general position, closely related to the Happy Ending problem.^{[6]}
Complexity
In general, determining the crossing number of a graph is hard; Garey and Johnson showed in 1983 that it is an NPhard problem.^{[7]} In fact the problem remains NPhard even when restricted to cubic graphs.^{[8]} More specifically, determining the rectilinear crossing number is complete for the existential theory of the reals.^{[9]}
On the positive side, there are efficient algorithms for determining if the crossing number is less than a fixed constant k — in other words, the problem is fixedparameter tractable.^{[10]} It remains difficult for larger k, such as V/2. There are also efficient approximation algorithms for approximating cr(G) on graphs of bounded degree.^{[11]} In practice heuristic algorithms are used, such as the simple algorithm which starts with no edges and continually adds each new edge in a way that produces the fewest additional crossings possible. These algorithms are used in the Rectilinear Crossing Number^{[12]} distributed computing project.
Crossing numbers of cubic graphs
The smallest cubic graphs with crossing numbers 1–8 are known (sequence A110507 in OEIS). The smallest 1crossing cubic graph is the complete bipartite graph K_{3,3}, with 6 vertices. The smallest 2crossing cubic graph is the Petersen graph, with 10 vertices. The smallest 3crossing cubic graph is the Heawood graph, with 14 vertices. The smallest 4crossing cubic graph is the MöbiusKantor graph, with 16 vertices. The smallest 5crossing cubic graph is the Pappus graph, with 18 vertices. The smallest 6crossing cubic graph is the Desargues graph, with 20 vertices. None of the four 7crossing cubic graphs, with 22 vertices, are well known.^{[13]} The smallest 8crossing cubic graph is the McGee graph or (3,7)cage graph, with 24 vertices.
In 2009, Exoo conjectured that the smallest cubic graph with crossing number 11 is the Coxeter graph, the smallest cubic graph with crossing number 13 is the Tutte–Coxeter graph and the smallest cubic graph with crossing number 170 is the Tutte 12cage.^{[14]}^{[15]}
The crossing number inequality
The very useful crossing number inequality, discovered independently by Ajtai, Chvátal, Newborn, and Szemerédi^{[16]} and by Leighton,^{[17]} asserts that if a graph G (undirected, with no loops or multiple edges) with n vertices and e edges satisfies
then we have
The constant 33.75 is the best known to date, and is due to Pach and Tóth;^{[18]} the constant 7.5 can be lowered to 4, but at the expense of replacing 33.75 with the worse constant of 64.
The motivation of Leighton in studying crossing numbers was for applications to VLSI design in theoretical computer science. Later, Székely^{[19]} also realized that this inequality yielded very simple proofs of some important theorems in incidence geometry, such as Beck's theorem and the SzemerédiTrotter theorem, and Tamal Dey used it to prove upper bounds on geometric ksets.^{[20]}
For graphs with girth larger than 2r and e ≥ 4n, Pach, Spencer and Tóth^{[21]} demonstrated an improvement of this inequality to
Proof of crossing number inequality
We first give a preliminary estimate: for any graph G with n vertices and e edges, we have
To prove this, consider a diagram of G which has exactly cr(G) crossings. Each of these crossings can be removed by removing an edge from G. Thus we can find a graph with at least edges and n vertices with no crossings, and is thus a planar graph. But from Euler's formula we must then have , and the claim follows. (In fact we have for n ≥ 3).
To obtain the actual crossing number inequality, we now use a probabilistic argument. We let 0 < p < 1 be a probability parameter to be chosen later, and construct a random subgraph H of G by allowing each vertex of G to lie in H independently with probability p, and allowing an edge of G to lie in H if and only if its two vertices were chosen to lie in H. Let e_{H} denote the number of edges of H, and let n_{H} denote the number of vertices.
Now consider a diagram of G with cr(G) crossings. We may assume that any two edges in this diagram with a common vertex are disjoint, otherwise we could interchange the intersecting parts of the two edges and reduce the crossing number by one. Thus every crossing in this diagram involves four distinct vertices of G.
Since H is a subgraph of G, this diagram contains a diagram of H; let denote the number of crossings of this random graph. By the preliminary crossing number inequality, we have
Taking expectations we obtain
Since each of the n vertices in G had a probability p of being in H, we have . Similarly, since each of the edges in G has a probability p^{2} of remaining in H (since both endpoints need to stay in H), then . Finally, every crossing in the diagram of G has a probability p^{4} of remaining in H, since every crossing involves four vertices, and so . Thus we have
If we now set p to equal 4n/e (which is less than one, since we assume that e is greater than 4n), we obtain after some algebra
A slight refinement of this argument allows one to replace 64 by 33.75 when e is greater than 7.5 n.^{[18]}
Notes
 ^ Turán, P. (1977). "A Note of Welcome". J. Graph Theory 1: 7–9. doi:10.1002/jgt.3190010105.
 ^ Zarankiewicz, K. (1954). "On a Problem of P. Turán Concerning Graphs". Fund. Math. 41: 137–145.
 ^ ^{a} ^{b} Guy, R.K. (1960). "A combinatorial problem". Nabla (Bulletin of the Malayan Mathematical Society) 7: 68–72.
 ^ de Klerk, E.; Maharry, J.; Pasechnik, D. V.; Richter, B.; Salazar, G. (2006). "Improved bounds for the crossing numbers of K_{m,n} and K_{n}". SIAM Journal on Discrete Mathematics 20 (1): 189–202. doi:10.1137/S0895480104442741. http://arno.uvt.nl/show.cgi?fid=71701.
 ^ Barát, János; Tóth, Géza (2009). "Towards the Albertson Conjecture". arXiv:0909.0413 [math.CO].
 ^ Scheinerman, Edward R.; Wilf, Herbert S. (1994). "The rectilinear crossing number of a complete graph and Sylvester's "four point problem" of geometric probability". American Mathematical Monthly 101 (10): 939–943. doi:10.2307/2975158. JSTOR 2975158.
 ^ Garey, M. R.; Johnson, D. S. (1983). "Crossing number is NPcomplete". SIAM J. Alg. Discr. Meth. 4 (3): 312–316. doi:10.1137/0604033. MR0711340.
 ^ Hliněný, P. (2006). "Crossing number is hard for cubic graphs". Journal of Combinatorial Theory, Series B 96 (4): 455–471. doi:10.1016/j.jctb.2005.09.009. MR2232384.
 ^ Schaefer, Marcus (2010). "Complexity of Some Geometric and Topological Problems". Graph Drawing, 17th International Symposium, GS 2009, Chicago, IL, USA, September 2009, Revised Papers. Lecture Notes in Computer Science. 5849. SpringerVerlag. pp. 334–344. doi:10.1007/9783642118050_32. ISBN 9783642118043. http://ovid.cs.depaul.edu/documents/convex.pdf.
 ^ Grohe, M. (2005). "Computing crossing numbers in quadratic time". J. Comput. System Sci. 68 (2): 285–302. doi:10.1016/j.jcss.2003.07.008. MR2059096; Kawarabayashi, Kenichi; Reed, Bruce (2007). "Computing crossing number in linear time". Proceedings of the 29th Annual ACM Symposium on Theory of Computing. pp. 382–390. doi:10.1145/1250790.1250848. ISBN 9781595936318.
 ^ Even, Guy; Guha, Sudipto; Schieber, Baruch (2003). "Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas". SIAM Journal on Computing 32 (1): 231–252. doi:10.1137/S0097539700373520.
 ^ Rectilinear Crossing Number on the Institute for Software Technology at Graz, University of Technology (2009).
 ^ Weisstein, Eric W., "Graph Crossing Number" from MathWorld.
 ^ Exoo, G.. "Rectilinear Drawings of Famous Graphs". http://isu.indstate.edu/ge/COMBIN/RECTILINEAR/.
 ^ Pegg, E. T.; Exoo, G. (2009). "Crossing Number Graphs". Mathematica J. 11.
 ^ Ajtai, M.; Chvátal, V.; Newborn, M.; Szemerédi, E. (1982). "Crossingfree subgraphs". Theory and Practice of Combinatorics. NorthHolland Mathematics Studies. 60. pp. 9–12. MR0806962.
 ^ Leighton, T. (1983). Complexity Issues in VLSI. Foundations of Computing Series. Cambridge, MA: MIT Press.
 ^ ^{a} ^{b} Pach, J.; Tóth, G. (1997). "Graphs drawn with few crossings per edge". Combinatorica 17 (3): 427–439. doi:10.1007/BF01215922. MR1606052.
 ^ Székely, L. A. (1997). "Crossing numbers and hard Erdős problems in discrete geometry". Combinatorics, Probability and Computing 6 (3): 353–358. doi:10.1017/S0963548397002976. MR1464571.
 ^ Dey, T. L. (1998). "Improved bounds for planar ksets and related problems". Discrete and Computational Geometry 19 (3): 373–382. doi:10.1007/PL00009354. MR1608878.
 ^ Pach, János; Spencer, Joel; Tóth, Géza (2000). "New bounds on crossing numbers". Discrete and Computational Geometry 24 (4): 623–644.
Categories: Topological graph theory
 Inequalities
 Graph invariants
Wikimedia Foundation. 2010.
Look at other dictionaries:
Crossing number — may refer to: Crossing number (knot theory) of a knot is the minimal number of crossings in any knot diagram for the knot. The average crossing number is a variant of crossing number obtained from a three dimensional embedding of a knot by… … Wikipedia
graph theory — Math. the branch of mathematics dealing with linear graphs. [1965 70] * * * Mathematical theory of networks. A graph consists of nodes (also called points or vertices) and edges (lines) connecting certain pairs of nodes. An edge that connects a… … Universalium
Glossary of graph theory — Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with… … Wikipedia
Minor (graph theory) — In graph theory, an undirected graph H is called a minor of the graph G if H is isomorphic to a graph that can be obtained by zero or more edge contractions on a subgraph of G. The theory of graph minors began with Wagner s theorem that a graph… … Wikipedia
Cut (graph theory) — In graph theory, a cut is a partition of the vertices of a graph into two disjoint subsets. The cut set of the cut is the set of edges whose end points are in different subsets of the partition. Edges are said to be crossing the cut if they are… … Wikipedia
Topological graph theory — In mathematics topological graph theory is a branch of graph theory. It studies the embedding of graphs in surfaces, and graphs as topological spaces. [J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987] Embedding a… … Wikipedia
Geometric graph theory — In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs. Notable geometric… … Wikipedia
Graph coloring — A proper vertex coloring of the Petersen graph with 3 colors, the minimum number possible. In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called colors to elements of a graph… … Wikipedia
Graph drawing — This article is about the general subject of graph drawing. For the annual research symposium, see International Symposium on Graph Drawing. Graphic representation of a minute fraction of the WWW, demonstrating hyperlinks. Graph drawing is an… … Wikipedia
number game — Introduction any of various puzzles and games that involve aspects of mathematics. Mathematical recreations comprise puzzles and games that vary from naive amusements to sophisticated problems, some of which have never been solved.… … Universalium