Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12 | Combinatorica Skip to main content
Springer Nature Link
Log in

Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12

  • Original paper
  • Published:
Combinatorica Aims and scope Submit manuscript

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 arbitrarily many vertices 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.1

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Pinontoan and R. B. Richter: Crossing numbers of sequences of graphs II: planar tiles, J. Graph Theory 42 (2003), 332–341.

    Article  MathSciNet  MATH  Google Scholar 

  2. B. Mohar and C. Thomassen: Graphs on Surfaces, Johns Hopkins University Press, 2001.

  3. B. Mohar, R. J. Nowakowski and D. B. West: Research problems from the 5th Slovenian Conference (Bled, 2003), Discrete Math. 307 (2007), 650–658.

    Article  MathSciNet  MATH  Google Scholar 

  4. C. Hernández-Vélez, G. Salazar and R. Thomas: Nested cycles in large triangulations and crossing-critical graphs, J. Comb. Theory, Series B 102 (2012), 86–92.

    Article  MathSciNet  MATH  Google Scholar 

  5. D. Bokal: Infinite families of crossing-critical graphs with prescribed average degree and crossing number, J. Graph Theory 65 (2010), 139–162.

    Article  MathSciNet  MATH  Google Scholar 

  6. D. Bokal, B. Oporowski, R. B. Richter and G. Salazar: Characterizing 2-crossing-critical graphs, Advances in Appl. Math. 74 (2016), 23–208.

    Article  MathSciNet  MATH  Google Scholar 

  7. D. Bokal, M. Chimani and J. Leaños: Crossing number additivity over edge cuts, Eur. J. Comb. 34 (2013), 1010–1018.

    Article  MathSciNet  MATH  Google Scholar 

  8. D. Bokal, M. Bračič, M. Dernár and P. HlinĕNú: On degree properties of crossing-critical families of graphs, Electron. J. Comb. 26 (2019), #P1.40.

    MathSciNet  MATH  Google Scholar 

  9. D. Bokal, Z. Dvorák, P. Hlinĕnú, J. Leaños, B. Mohar and T. Wiedera: Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12, in: Gill Barequet and Yusu Wang, editors, 35th International Symposium on Computational Geometry (SoCG 2019), volume 129 of Leibniz International Proceedings in Informatics (LIPIcs), 14, 1–15, 2019, Schloss Dagstuhl—Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany.

    Google Scholar 

  10. J. Leaños and G. Salazar: On the additivity of crossing numbers of graphs, Journal of Knot Theory and Its Ramifications — JKTR 17 (2008), 1043–1050.

    Article  MathSciNet  MATH  Google Scholar 

  11. J. Geelen, R. B. Richter and G. Salazar: Embedding grids in surfaces, European Journal of Combinatorics 25 (2004), 785–792.

    Article  MathSciNet  MATH  Google Scholar 

  12. F. T. Leighton: Complexity Issues in VLSI: Optimal Layouts for the Shuffle-exchange Graph and Other Networks, MIT Press, Cambridge, MA, USA, 1983.

    Google Scholar 

  13. M. Chimani and T. Wiedera: An ILP-based proof system for the crossing number problem, in: ESA 2016, LIPIcs 57, 29, 1–13, 2016, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany.

    Google Scholar 

  14. M. Kochol: Construction of crossing-critical graphs, Discrete Math. 66 (1987), 311–313.

    Article  MathSciNet  MATH  Google Scholar 

  15. M. Ajtai, V. Chvátal, M. M. Newborn and E. Szemerádi: Crossing-Free Subgraphs, volume 60 of North-Holland Mathematics Studies, North-Holland, 1982.

  16. P. Hlinĕný: Crossing-number critical graphs have bounded path-width, J. Comb. Theory, Series B 88 (2003), 347–367.

    Article  MathSciNet  MATH  Google Scholar 

  17. P. Hlinĕný and G. Salazar: Stars and bonds in crossing-critical graphs, J. Graph Theory 65 (2010), 198–215.

    Article  MathSciNet  MATH  Google Scholar 

  18. P. Hlinĕná and M. Korbela: On 13-crossing-critical graphs with arbitrarily large degrees, 2021, in: Extended Abstracts EuroComb 2021, Trends in Mathematics, 50–56, Springer, 2021.

  19. R. B. Richter and C. Thomassen: Minimal graphs with crossing number at least k, J. Comb. Theory, Series B 58 (1993), 217–224.

    Article  MathSciNet  MATH  Google Scholar 

  20. J. Širáň: Infinite families of crossing-critical graphs with a given crossing number, Discrete Math. 48 (1984), 129–132.

    Article  MathSciNet  MATH  Google Scholar 

  21. Z. Dvořák and B. Mohar: Crossing-critical graphs with large maximum degree, J. Comb. Theory, Series B 100 (2010), 413–417.

    Article  MathSciNet  MATH  Google Scholar 

  22. Z. Dvořák, P. Hlinřný and B. Mohar: Structure and generation of crossing-critical graphs, in: SoCG 2018, LIPIcs 99, 33, 1–14, 2018, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany.

    Google Scholar 

Download references

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.

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia

    Drago Bokal

  2. Computer Science Institute, Charles University, Prague, Czech Republic

    Zdenĕk Dvořák

  3. Faculty of Informatics, Masaryk University, Brno, Czech Republic

    Petr Hlinĕný

  4. Academic Unit of Mathematics, Autonomous University of Zacatecas, Zacatecas, Mexico

    Jesús Leaños

  5. Department of Mathematics, Simon Fraser University, Burnaby, BC, Canada

    Bojan Mohar

  6. Institute of Mathematics Physics, and Mechanics, Ljubljana, Slovenia

    Bojan Mohar

  7. Theoretical Computer Science, Osnabrück University, Osnabrück, Germany

    Tilo Wiedera

Authors
  1. Drago Bokal
    View author publications

    You can also search for this author inPubMed Google Scholar

  2. Zdenĕk Dvořák
    View author publications

    You can also search for this author inPubMed Google Scholar

  3. Petr Hlinĕný
    View author publications

    You can also search for this author inPubMed Google Scholar

  4. Jesús Leaños
    View author publications

    You can also search for this author inPubMed Google Scholar

  5. Bojan Mohar
    View author publications

    You can also search for this author inPubMed Google Scholar

  6. Tilo Wiedera
    View author publications

    You can also search for this author inPubMed Google Scholar

Corresponding author

Correspondence to Jesús Leaños.

Additional information

Drago Bokal was supported by ARRS Projects J1-8130, J1-2452 and ARRS Programme P1-0297.

Zdenĕk Dvořák was supported by project 17-04611S (Ramsey-like aspects of graph coloring) of Czech Science Foundation.

Petr Hlinĕný was supported by projects 17-00837S and 20-04567S of Czech Science Foundation.

Jesús Leaños was partially supported by PFCE-UAZ 2018-2019 grant.

Bojan Mohar was supported in part by the NSERC Discovery Grant R611450 (Canada), by the Canada Research Chairs program, and by the Research Projects J1-8130 and J1-2452 of ARRS (Slovenia).

Tilo Wiedera was supported by the German Research Foundation (DFG) project CH 897/2-2.

This work is based on a SoCG contribution [9] and gives full proofs and a significant strengthening of the announced results.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Bokal, D., Dvořák, Z., Hlinĕný, P. et al. Bounded Degree Conjecture Holds Precisely for c-Crossing-Critical Graphs with c ≤ 12. Combinatorica 42, 701–728 (2022). https://doi.org/10.1007/s00493-021-4285-3

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00493-021-4285-3

Mathematics Subject Classification (2010)