Computing crossing number in linear time

ABSTRACT

We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time.

Our algorithm can also be compared to the algorithms by Mohar (STOC'96 and Siam J. Discrete Math 2001), for testing the embeddability of an input graph in a fixed surface. For each surface s, Mohar describes an algorithm which yields either an embedding of G in s or a minor of G which is not embeddable in s and is minimal with this property.

The same approach allows us to obtain linear time algorithms for the same question for a variety of other crossing numbers. We can also determine in linear time if an input graph can be made planar by the deletion of k edges (for fixed k).

REFERENCES

• 1: M. Ajtai, V. Chvátal, M. Newborn and E. Szemerédi, Crossing-free subgraphs, in "Theory and Practice of Combinatorics" 60 9--12. North-Holland Math. Stud., North-Holland, Amsterdam/New York, 1982.
• 2: Stefan Arnborg , Andrzej Proskurowski, Linear time algorithms for NP-hard problems restricted to partial k-trees, Discrete Applied Mathematics, v.23 n.1, p.11-24, April 1989 [doi>10.1016/0166-218X(89)90031-0]
• 3: S.N. Bhatt and F.T. leighton, A framework for solving VLSI graph layout problem, J. Comput. System Sci. 28 (1984), 300--343.
• 4: Daniel Bienstock, Some provably hard crossing number problems, Discrete & Computational Geometry, v.6 n.5, p.443-459, 1991 [doi>10.1007/BF02574701]
• 5: E. Birmelé, J.A. Bondy and B. A. Reed, The Erdös-Pòsa property for long circuits, preprint.
• 6: John Adrian Bondy, Graph Theory With Applications, Elsevier Science Ltd, 1976
• 7: K. S. Booth and G.S. Lueker, Testing for the consecutive ones property, interval graphs and graph planarity using PQ-trees, J. Comput. System Sci. 13 (1976), 335--379.
• 8: Hans L. Bodlaender, A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth, SIAM Journal on Computing, v.25 n.6, p.1305-1317, Dec. 1996 [doi>10.1137/S0097539793251219]
• 9: T. Brahana, Systems of circuits on 2-dimensional manifolds, Ann. Math., 23, (1921), 144--168.
• 10: Richard Brunet , Bojan Mohar , R. Bruce Richter, Separating and nonseparating disjoint homotopic cycles in graph embeddings, Journal of Combinatorial Theory Series B, v.66 n.2, p.201-231, March 1996 [doi>10.1006/jctb.1996.0016]
• 11: S. Cabello and B. Mohar, Finding shortest non-separating and non-contractible cycles for topologically embedded graphs, submitted.
• 12: S. Cabello and B. Mohar, Problem of months, Fall 2005, http://www.fmf.uni-lj.si/~mohar/
• 13: Brouno Courcelle, Graph rewriting: an algebraic and logic approach, Handbook of theoretical computer science (vol. B): formal models and semantics, MIT Press, Cambridge, MA, 1991
• 14: R. Diestel, Graph Theory, 2nd Edition, Springer, 2000.
• 15: Reinhard Diestel , Tommy R. Jensen , Konstantin Yu. Gorbunov , Carsten Thomassen, Highly connected sets and the excluded grid theorem, Journal of Combinatorial Theory Series B, v.75 n.1, p.61-73, Jan. 1999 [doi>10.1006/jctb.1998.1862]
• 16: R.G. Downey and M.R. Fellows, Parameterized complexity, Springer-Verlag, 1999.
• 17: Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513430]
• 18: Guy Even , Sudipto Guha , Baruch Schieber, Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas, SIAM Journal on Computing, v.32 n.1, p.231-252, 2003 [doi>10.1137/S0097539700373520]
• 19: Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
• 20: I. S. Filotti , Gary L. Miller , John Reif, On determining the genus of a graph in O(v O(g)) steps(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.27-37, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804395]
• 21: E. Garcia-Moreno and G. Salazar, Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree, J. Graph Theory 36 (2001), 168--173.
• 22: M.R. Garey and D.S. Johnson. The NP-completeness column: An ongoing guide. J. Algorithm. 3 89--99, (1982).
• 23: J. F. Geelen , R. B. Richter , G. Salazar, Embedding grids in surfaces, European Journal of Combinatorics, v.25 n.6, p.785-792, August 2004 [doi>10.1016/j.ejc.2003.07.007]
• 24: Martin Grohe, Computing crossing numbers in quadratic time, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.231-236, July 2001, Hersonissos, Greece [doi>10.1145/380752.380805]
• 25: R. Halin, s-function for graphs, J. Geometry 8 (1976), 171--186.
• 26: John Hopcroft , Robert Tarjan, Efficient Planarity Testing, Journal of the ACM (JACM), v.21 n.4, p.549-568, Oct. 1974 [doi>10.1145/321850.321852]
• 27: D. J. Kleitman, The crossing number of K^5,n, J. Combin. Theory 9 (1970), 315--323.
• 28: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 29: F.T. Leighton, Complexity issues in VLSI, MIT Press, Cambridge, MA, 1993.
• 30: F. T. Leighton, New lower bound techiques for VLSI, Math. Systems Theory 17 (1984), 47--70.
• 31: Bojan Mohar, Embedding graphs in an arbitrary surface in linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.392-397, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237986]
• 32: Bojan Mohar, A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface, SIAM Journal on Discrete Mathematics, v.12 n.1, p.6-26, Jan. 1999 [doi>10.1137/S089548019529248X]
• 33: Bojan Mohar, Face covers and the genus problem for Apex graphs, Journal of Combinatorial Theory Series B, v.82 n.1, p.102-117, May 2001 [doi>10.1006/jctb.2000.2026]
• 34: B. Mohar and C. Thomassen, Graphs on Surfaces, Johns Hopkins University Press, Baltimore, MD, 2001.
• 35: J. Pach, J. Spencer and G. Tóth, New bounds on crossing numbers, Discrete Comput. Geom. 24 (2000), 623--644.
• 36: J. Pach and G. Tóth, Graphs drawn with few crossing per edges, Combinatorica 17 (1997), 427--439.
• 37: J. Pach , G. Tòth, Which Crossing Number is it, Anyway?, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.617, November 08-11, 1998
• 38: János Pach , Radoš Radoicić , Gábor Tardos , Géza Tóth, Improving the crossing lemma by finding more crossings in sparse graphs: [extended abstract], Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA [doi>10.1145/997817.997831]
• 39: L. Pérkovic and B. Reed, An improved algorithm for finding tree decompositions of small width; International Journal on the Foundations of Computing Science., 11, (2000), 81--85.
• 40: B. Reed, Tree width and tangles: a new connectivity measure and some applications, in "Surveys in Combinatorics, 1997 (London)" , London Math. Soc. Lecture Note Ser. 241, Cambridge Univ. Press, Cambridge, 1997, pp87--162.
• 41: Bruce Reed, Rooted routing in the plane, Discrete Applied Mathematics, v.57 n.2-3, p.213-227, Feb. 24, 1995 [doi>10.1016/0166-218X(94)00104-L]
• 42: B. Reed, N. Robertson, A. Schrijver and P. D. Seymour, Finding disjoint trees in planar graphs in linear time. Graph structure theory (Seattle, WA, 1991), 295--301, Contemp. Math., 147, Amer. Math. Soc., Providence, RI, 1993.
• 43: R.B. Richter and C. Thomassen, Relations between crossing numbers of complete and complete bipartite graphs, Amer. Math. Monthly, Feburary (1997), 131--137.
• 44: N. Robertson and P.D. Seymour, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithm 7 (1986), 309--322.
• 45: Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
• 46: Neil Robertson , P. D. Seymour, Graph minors. XIII: the disjoint paths problem, Journal of Combinatorial Theory Series B, v.63 n.1, p.65-110, Jan. 1995 [doi>10.1006/jctb.1995.1006]
• 47: Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
• 48: P. D. Seymour , Robin Thomas, Graph searching and a min-max theorem for tree-width, Journal of Combinatorial Theory Series B, v.58 n.1, p.22-33, May 1993 [doi>10.1006/jctb.1993.1027]
• 49: Joel Spencer , Géza Tóth, Crossing numbers of random graphs, Random Structures & Algorithms, v.21 n.3-4, p.347-358, October 2002 [doi>10.1002/rsa.10053]
• 50: László A. Székely, Crossing Numbers and Hard Erdös Problems in Discrete Geometry, Combinatorics, Probability and Computing, v.6 n.3, p.353-358, September 1997 [doi>10.1017/S0963548397002976]
• 51: C. Thomassen, The graph genus problem is NP-complete, Journal of Algorithms, v.10 n.4, p.568-576, Dec. 1989 [doi>10.1016/0196-6774(89)90006-0]
• 52: Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]
• 53: S. G. Williamson, Depth-First Search and Kuratowski Subgraphs, Journal of the ACM (JACM), v.31 n.4, p.681-693, Oct. 1984 [doi>10.1145/1634.322451]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

Keywords:
crossing number, linear time algorithm, tree-width