Crossing Number of Graphs with Rotation Systems

Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2008) Crossing Number of Graphs with Rotation Systems. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 3-12 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_3).

Full text not available from this repository.

Abstract

We show that computing the crossing number of a graph with a given rotation system is NP-complete. This result leads to a new and much simpler proof of Hlinvený's result, that computing the crossing number of a cubic graph (without rotation system) is NP-complete. We also investigate the special case of multigraphs with rotation systems on a fixed number $k$ of vertices. For k=1 and k=2 the crossing number can be computed in polynomial time and approximated to within a factor of 2 in linear time. For larger k we show how to approximate the crossing number to within a factor of k+4choose 4/5 in time O(m^k+2) on a graph with m edges.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-77537-9_3
Classifications:G Algorithms and Complexity > G.420 Crossings
ID Code:823

Repository Staff Only: item control page

References

Dan Archdeacon. Problems in topological graph theory. http://www.emba.uvm.edu/~archdeac/problems/npcubic.htm (accessed September 15th, 2006).

Drago Bokal, Gasper Fijavz, and Bojan Mohar. Minor-monotone crossing number. In Stefan Felsner, editor, EuroComb '05, volume AE, pages 123-128. Discrete Mathematics and Theoretical Computer Science, 2005.

Christoph Buchheim, Michael Jünger, Annette Menze, and Merijam Percan. Directed crossing minimization. Technical report, Zentrum für Angewandte Informatik Köln, Lehrstuhl Jünger, August 2005.

Persi Diaconis and R. L. Graham. Spearman's footrule as a measure of disarray. J. Roy. Statist. Soc. Ser. B, 39(2):262-268, 1977.

Michael Garey and David Johnson. Crossing number is NP-complete. SIAM Journal on Algebraic and Discrete Methods, 4:312-316, 1983.

Petr Hlinený. Crossing number is hard for cubic graphs. J. Combin. Theory Ser. B, 96(4):455-471, 2006.

Zvi M. Kedem and Henry Fuchs. On finding several shortest paths in certain graphs. In 18th Allerton Conference, pages 677-686, 1980.

Donald E. Knuth. The art of computer programming. Volume 3. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1973. Sorting and searching , Addison-Wesley Series in Computer Science and Information Processing.

Roy Lowrance and Robert A. Wagner. An extension of the string-to-string correction problem. J. Assoc. Comput. Mach., 22:177-183, 1975.

Maurice Maes. On a cycling string-to-string correction problem. Inform. Process. Lett., 35(2):73-78, 1990.

Andrés Marzal and Sergio Barrachina. Speeding up the computation of the edit distance for cyclic strings. In International Conference on Pattern Recognition, pages 891-894, 2000.

Daniel Stefankovic Michael J. Pelsmajer, Marcus Schaefer. Removing even crossings. In Stefan Felsner, editor, EuroComb '05, volume AE of DMTCS Proceedings, pages 105-110. Discrete Mathematics and Theoretical Computer Science, 2005.

Michael J. Pelsmajer, Marcus Schaefer, and Daniel Stefankovic. Odd crossing number is not crossing number. In Patrick Healy and Nikola S. Nikolov, editors, Graph Drawing, volume 3843 of Lecture Notes in Computer Science, pages 386-396. Springer, 2005.

Michael J. Pelsmajer, Marcus Schaefer, and Daniel Stefankovic. Removing even crossings. J. Combin. Theory Ser. B, 2006. To appear.

Robert A. Wagner. On the complexity of the extended string-to-string correction problem. In Seventh Annual ACM Symposium on Theory of Computing (Albuquerque, N. M., 1975), pages 218-223. Assoc. Comput. Mach., New York, 1975.