Computing crossing numbers in quadratic time

ABSTRACT

We show that for every fixed k\ge 0 there is a quadratic time algorithm that decides whether 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.

REFERENCES

• 1: 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]
• 2: S.S. Cosmadakis. Logical reducibility and monadic NP. In Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, pages 52-61, 1993.
• 3: 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
• 4: B. Courcelle, The expression of graph properties and graph transformations in monadic second-order logic, Handbook of graph grammars and computing by graph transformation: volume I. foundations, World Scientific Publishing Co., Inc., River Edge, NJ, 1997
• 5: Bruno Courcelle, The monadic second-order logic of graphs XII: planar graphs and planar maps, Theoretical Computer Science, v.237 n.1-2, p.1-32, April 28, 2000 [doi>10.1016/S0304-3975(99)00305-9]
• 6: R.G. Downey and M.R. Fellows. Parameterized Complexity. Springer-Verlag, 1999.
• 7: H.-D. Ebbinghaus, J. Flum, and W. Thomas. Mathematical Logic. Springer-Verlag, 2nd edition, 1994.
• 8: 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]
• 9: M.R. Fellows and U. Stege. An improved fixed-parameter-tractable algorithm for vertex cover. Technical Report 318, Department of Computer Science, ETH Zurich, 1999.
• 10: 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]
• 11: Jörg Flum , Markus Frick , Martin Grohe, Query Evaluation via Tree-Decompositions, Proceedings of the 8th International Conference on Database Theory, p.22-38, January 04-06, 2001
• 12: M.R. Garey and D.S. Johnson. The NP-completeness column: An ongoing guide. Journal of Algorithms, 3:89-99, 1982.
• 13: 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]
• 14: 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]
• 15: 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]
• 16: 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]
• 17: 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]
• 18: Carsten Thomassen, A simpler proof of the excluded minor theorem for higher surfaces, Journal of Combinatorial Theory Series B, v.70 n.2, p.306-311, July 1997 [doi>10.1006/jctb.1997.1761]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

General Terms:
Algorithms, Performance, Theory, Verification