Document Open Access Logo

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

PDF

File

Thumbnail PDF
PDF
LIPIcs.SoCG.2019.14.pdf
  • Filesize: 0.55 MB
  • 15 pages

Document Identifiers

Related Versions

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Drago Bokal
  • Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia
Zdeněk Dvořák
  • Computer Science Institute, Charles University, Prague, Czech Republic
Petr Hliněný
  • Faculty of Informatics, Masaryk University, Brno, Czech Republic
Jesús Leaños
  • Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico
Bojan Mohar
  • Department of Mathematics, Simon Fraser University, Burnaby BC, Canada
  • Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia
Tilo Wiedera
  • Theoretical Computer Science, Osnabrück University, Germany

Funding

  • Bokal, Drago: ARRS Project J1-8130, ARRS Programme P1-0297.
  • Dvořák, Zdeněk: Supported by project 17-04611S of Czech Science Foundation.
  • Hliněný, Petr: Supported by Czech Science Foundation, project no. 17-00837S.
  • Leaños, Jesús: Partially supported by PFCE-UAZ 2018-2019 grant.
  • Mohar, Bojan: B.M. was supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada Research Chairs program, and by the Research Project J1-8130 of ARRS (Slovenia).
  • Wiedera, Tilo: Supported by the German Research Foundation (DFG) project CH 897/2-2.

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.

References

  1. 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.
  2. 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.
  3. 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. Google Scholar
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. Frank T. Leighton. Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks. MIT Press, Cambridge, MA, USA, 1983. Google Scholar
  14. 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.
  15. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001. URL: https://jhupbooks.press.jhu.edu/content/graphs-surfaces.
  16. 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.
  17. 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.
  18. 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.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact