LIPIcs.SoCG.2018.33.pdf
- Filesize: 0.55 MB
- 14 pages
Document
Structure and Generation of Crossing-Critical Graphs
Authors
-
Part of:
Volume:
34th International Symposium on Computational Geometry (SoCG 2018)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2018-06-08
Cite AsGet BibTex
Zdenek Dvorák, Petr Hlinený, and Bojan Mohar. Structure and Generation of Crossing-Critical Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.33
https://doi.org/10.4230/LIPIcs.SoCG.2018.33
Abstract
We study c-crossing-critical graphs, which are the minimal graphs that require at least c edge-crossings when drawn in the plane. For c=1 there are only two such graphs without degree-2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
Keywords
- crossing number
- crossing-critical
- path-width
- exhaustive generation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- M. Ajtai, V. Chvátal, M.M. Newborn, and E. Szemerédi. Crossing-free subgraphs. In Theory and Practice of Combinatorics, volume 60 of North-Holland Mathematics Studies, pages 9-12. North-Holland, 1982. URL: http://dx.doi.org/10.1016/S0304-0208(08)73484-4.
- Drago Bokal. Infinite families of crossing-critical graphs with prescribed average degree and crossing number. Journal of Graph Theory, 65(2):139-162, 2010. URL: http://dx.doi.org/10.1002/jgt.20470.
- Drago Bokal, Bogdan Oporowski, R. Bruce Richter, and Gelasio Salazar. Characterizing 2-crossing-critical graphs. Advances in Applied Mathematics, 74:23-208, 2016. URL: http://dx.doi.org/10.1016/j.aam.2015.10.003.
- Thomas Colcombet. Factorization forests for infinite words and applications to countable scattered linear orderings. Theor. Comput. Sci., 411(4-5):751-764, 2010. URL: http://dx.doi.org/10.1016/j.tcs.2009.10.013.
- Z. Dvořák and B. Mohar. Crossing-critical graphs with large maximum degree. J. Combin. Theory, Ser. B, 100:413-417, 2010. URL: http://dx.doi.org/10.1016/j.jctb.2009.11.003.
- C. Hernandez-Velez, G. Salazar, and R. Thomas. Nested cycles in large triangulations and crossing-critical graphs. Journal of Combinatorial Theory, Series B, 102:86-92, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.04.006.
- P. Hliněný. Crossing-number critical graphs have bounded path-width. J. Combin. Theory, Ser. B, 88:347-367, 2003. URL: http://dx.doi.org/10.1016/S0095-8956(03)00037-6.
- P. Hliněný and G. Salazar. Stars and bonds in crossing-critical graphs. J. Graph Theory, 65:198-215, 2010. URL: http://dx.doi.org/10.1002/jgt.20473.
- Petr Hliněný. Crossing-critical graphs and path-width. In Petra Mutzel, Michael Jünger, and Sebastian Leipert, editors, Graph Drawing, 9th International Symposium, GD 2001, Revised Papers, volume LNCS 2265 of Lecture Notes in Computer Science, pages 102-114. Springer, 2002. URL: http://dx.doi.org/10.1007/3-540-45848-4_9.
- Petr Hliněný and Marek Dernár. Crossing number is hard for kernelization. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pages 42:1-42:10. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.42.
- Martin Kochol. Construction of crossing-critical graphs. Discrete Mathematics, 66(3):311-313, 1987. URL: http://dx.doi.org/10.1016/0012-365X(87)90108-7.
-
Tom Leighton. Complexity Issues in VLSI. Foundations of Computing Series. MIT Press, Cambridge, MA, 1983.
-
B. Mohar and C. Thomassen. Graphs on Surfaces. The Johns Hopkins University Press, Baltimore and London, 2001.
- Benny Pinontoan and R. Bruce Richter. Crossing numbers of sequences of graphs II: Planar tiles. Journal of Graph Theory, 42(4):332-341, 2003. URL: http://dx.doi.org/10.1002/jgt.10097.
- R. Bruce Richter and Carsten Thomassen. Minimal graphs with crossing number at least k. J. Comb. Theory, Ser. B, 58(2):217-224, 1993. URL: http://dx.doi.org/10.1006/jctb.1993.1038.
- Gelasio Salazar. Infinite families of crossing-critical graphs with given average degree. Discrete Mathematics, 271(1-3):343-350, 2003. URL: http://dx.doi.org/10.1016/S0012-365X(03)00136-5.
- Imre Simon. Factorization forests of finite height. Theor. Comput. Sci., 72(1):65-94, 1990. URL: http://dx.doi.org/10.1016/0304-3975(90)90047-L.
- László A. Székely. Crossing numbers and hard Erdös problems in discrete geometry. Combinatorics, Probability & Computing, 6(3):353-358, 1997. URL: http://journals.cambridge.org/action/displayAbstract?aid=46513.
- Jozef Širáň. Infinite families of crossing-critical graphs with a given crossing number. Discrete Mathematics, 48(1):129-132, 1984. URL: http://dx.doi.org/10.1016/0012-365X(84)90140-7.