Crossing Numbers and Parameterized Complexity

Pelsmajer, Michael J. and Schaefer, Marcus and Stefankovic, Daniel (2008) Crossing Numbers and Parameterized Complexity. In: Graph Drawing 15th International Symposium, GD 2007, September 24-26, 2007, Sydney, Australia , pp. 31-36 (Official URL: http://dx.doi.org/10.1007/978-3-540-77537-9_6).

Full text not available from this repository.

Abstract

The odd crossing number of G is the smallest number of pairs of edges that cross an odd number of times in any drawing of G. We show that there always is a drawing realizing the odd crossing number of G that uses at most 9^k crossings, where k is the odd crossing number of G. As a consequence of this and a result of Grohe we can show that the odd crossing number is fixed-parameter tractable.

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

Repository Staff Only: item control page

References

Martin Grohe. Computing crossing numbers in quadratic time. In Proceedings of the 32nd ACM Symposium on Theory of Computing, pages 231-236, july 6-8 2001.

Ken ichi Kawarabayashi and Bruce Reed. Computing crossing number in linear time. Accepted to STOC 2007.

Jan Kratochvíl and Jirí Matousek. String graphs requiring exponential representations. Journal of Combinatorial Theory, Series B, 53:1-4, 1991.

János Pach and Géza Tóth. Which crossing number is it anyway? J. Combin. Theory Ser. B, 80(2):225-246, 2000.

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. In Stefan Felsner, editor, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), volume AE of DMTCS Proceedings, pages 105-109. Discrete Mathematics and Theoretical Computer Science, April 2005.

Marcus Schaefer and Daniel Stefankovic. Decidability of string graphs. In Proceedings of the 33th Annual ACM Symposium on Theory of Computing (STOC-2001), pages 241-246, 2001.

Géza Tóth. Note on the pair-crossing number and the odd-crossing number. Unpublished manuscript.

Pavel Valtr. On the pair-crossing number. In Combinatorial and Computational Geometry, volume 52 of Math. Sci. Res. Inst. Publ., pages 569-575. Cambridge Univ. Press, Cambridge, 2005.