Bounded degree conjecture holds precisely for c-crossing-critical graphs with c ≤ 12
Autor(en): | Bokal, D. Dvořák, Z. Hliněný, P. Leaños, J. Mohar, B. Wiedera, T. |
Herausgeber: | Barequet, G. Wang, Y. |
Stichwörter: | Computational geometry; Critical graph; Crossing number; Crossing-critical; Drawing (graphics), Bounded degree; Edge crossing; Explicit constructions; Graph drawing; Maximum degree; Zip product; Zip product, Graph theory | Erscheinungsdatum: | 2019 | Herausgeber: | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing | Journal: | Leibniz International Proceedings in Informatics, LIPIcs | Volumen: | 129 | Zusammenfassung: | 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. © Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Jesús Leaños, Bojan Mohar, and Tilo Wiedera. |
Beschreibung: | Conference of 35th International Symposium on Computational Geometry, SoCG 2019 ; Conference Date: 18 June 2019 Through 21 June 2019; Conference Code:148855 |
ISBN: | 9783959771047 | ISSN: | 18688969 | DOI: | 10.4230/LIPIcs.SoCG.2019.14 | Externe URL: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-85068041340&doi=10.4230%2fLIPIcs.SoCG.2019.14&partnerID=40&md5=5cfa89a08620a63c84ff370c4f123533 |
Zur Langanzeige
Seitenaufrufe
4
Letzte Woche
0
0
Letzter Monat
1
1
geprüft am 01.06.2024