LIPIcs.SoCG.2019.14.pdf
- Filesize: 0.55 MB
- 15 pages
Document
Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12
Authors
Drago Bokal 
,
Zdeněk Dvořák ,
Petr Hliněný ,
Jesús Leaños ,
Bojan Mohar ,
Tilo Wiedera
-
Part of:
Volume:
35th International Symposium on Computational Geometry (SoCG 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Symposium on Computational Geometry (SoCG) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-06-11
File
Document Identifiers
Author Details
- Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia
- Department of Mathematics, Simon Fraser University, Burnaby BC, Canada
- Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia
Acknowledgements
We acknowledge the supporting environment of the workshop Crossing Numbers: Theory and Applications (18w5029) at the Banff International Research Station, where the fundamentals of this contribution were developed.
Cite As Get BibTex
Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, and Tilo Wiedera. Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c <= 12. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 14:1-14:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.SoCG.2019.14
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 every fixed pair of integers with c >= 13 and d >= 1, we give first explicit constructions of c-crossing-critical graphs containing a vertex of degree greater than d. We also show that such unbounded degree constructions do not exist for c <=12, precisely, that there exists a constant D such that every c-crossing-critical graph with c <=12 has maximum degree at most D. Hence, the bounded maximum degree conjecture of c-crossing-critical graphs, which was generally disproved in 2010 by Dvořák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
Subject Classification
ACM Subject Classification
- Theory of computation → Computational geometry
- Mathematics of computing → Graphs and surfaces
Keywords
- graph drawing
- crossing number
- crossing-critical
- zip product
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Miklós Ajtai, Vašek Chvátal, Monroe M. Newborn, and Endre Szemerédi. Crossing-Free Subgraphs. In Peter L. Hammer, Alexander Rosa, Gert Sabidussi, and Jean Turgeon, editors, 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. J. Graph Theory, 65(2):139-162, 2010. URL: http://dx.doi.org/10.1002/jgt.20470.
-
Drago Bokal, Mojca Bračič, Marek Dernár, and Petr Hliněný. On Degree Properties of Crossing-Critical Families of Graphs. Electron. J. Comb., 26(1):#P1.40, 2019.
- Drago Bokal, Markus Chimani, and Jesús Leaños. Crossing number additivity over edge cuts. Eur. J. Comb., 34(6):1010-1018, 2013. URL: http://dx.doi.org/10.1016/j.ejc.2013.02.002.
- Drago Bokal, Bogdan Oporowski, R. Bruce Richter, and Gelasio Salazar. Characterizing 2-crossing-critical graphs. Advances in Appl. Math., 74:23-208, 2016. URL: http://dx.doi.org/10.1016/j.aam.2015.10.003.
- Markus Chimani and Tilo Wiedera. An ILP-based Proof System for the Crossing Number Problem. In ESA 2016, LIPIcs 57, pages 29:1-29:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2016.29.
- Zdenek Dvořák, Petr Hliněný, and Bojan Mohar. Structure and Generation of Crossing-Critical Graphs. In SoCG 2018, LIPIcs 99, pages 33:1-33:14, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.33.
- Zdeněk Dvořák and Bojan Mohar. Crossing-critical graphs with large maximum degree. J. Comb. Theory, Series B, 100(4):413-417, 2010. URL: http://dx.doi.org/10.1016/j.jctb.2009.11.003.
- César Hernández-Vélez, Gelasio Salazar, and Robin Thomas. Nested cycles in large triangulations and crossing-critical graphs. J. Comb. Theory, Series B, 102(1):86-92, 2012. URL: http://dx.doi.org/10.1016/j.jctb.2011.04.006.
- Petr Hliněný. Crossing-number critical graphs have bounded path-width. J. Comb. Theory, Series B, 88(2):347-367, 2003. URL: http://dx.doi.org/10.1016/S0095-8956(03)00037-6.
- Martin Kochol. Construction of crossing-critical graphs. Discrete Math., 66(3):311-313, 1987. URL: http://dx.doi.org/10.1016/0012-365X(87)90108-7.
- Jesús Leaños and Gelasio Salazar. On the additivity of crossing numbers of graphs. Journal of Knot Theory and Its Ramifications - JKTR, 17:1043-1050, 2008. URL: http://dx.doi.org/10.1142/S0218216508006531.
-
Frank T. Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA, 1983.
- Bojan Mohar, Richard J. Nowakowski, and Douglas B. West. Research problems from the 5th Slovenian Conference (Bled, 2003). Discrete Math., 307(3-5):650-658, 2007. URL: http://dx.doi.org/10.1016/j.disc.2006.07.013.
- Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001. URL: https://jhupbooks.press.jhu.edu/content/graphs-surfaces.
- Benny Pinontoan and R. Bruce Richter. Crossing numbers of sequences of graphs II: Planar tiles. J. 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, Series B, 58(2):217-224, 1993. URL: http://dx.doi.org/10.1006/jctb.1993.1038.
- Jozef Širáň. Infinite families of crossing-critical graphs with a given crossing number. Discrete Math., 48(1):129-132, 1984. URL: http://dx.doi.org/10.1016/0012-365X(84)90140-7.