Bounded degree conjecture holds precisely for
c-crossing-critical graphs with c<=12

D 2019

Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR et. al.

Basic information

Original name

Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

Authors

BOKAL, Drago (705 Slovenia), Zdeněk DVOŘÁK (203 Czech Republic), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution), Jesus LEANOS (484 Mexico), Bojan MOHAR (705 Slovenia) and Tilo WIEDERA (276 Germany)

Edition

Dagstuhl, 35th International Symposium on Computational Geometry, SoCG 2019, p. "14:1"-"14:15", 15 pp. 2019

Publisher

Leibniz International Proceedings in Informatics, LIPIcs

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

electronic version available online

References:

open access

RIV identification code

RIV/00216224:14330/19:00108275

Organization unit

Faculty of Informatics

ISBN

978-3-95977-104-7

ISSN

DOI

http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14

Keywords in English

Crossing number; Crossing-critical; Exhaustive generation; Path-width

Abstract

V originále

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 Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.

Links

GA17-00837S, research and development project

Name: Strukturální vlastnosti, parametrizovaná řešitelnost a těžkost v kombinatorických problémech

Investor: Czech Science Foundation

Citovat

BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12. Online. In 35th International Symposium on Computational Geometry, SoCG 2019. Dagstuhl: Leibniz International Proceedings in Informatics, LIPIcs, 2019, p. "14:1"-"14:15", 15 pp. ISBN 978-3-95977-104-7. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14.

@inproceedings{1646176,
   author = {Bokal, Drago and Dvořák, Zdeněk and Hliněný, Petr and Leanos, Jesus and Mohar, Bojan and Wiedera, Tilo},
   address = {Dagstuhl},
   booktitle = {35th International Symposium on Computational Geometry, SoCG 2019},
   doi = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14},
   keywords = {Crossing number; Crossing-critical; Exhaustive generation; Path-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-104-7},
   pages = {"14:1"-"14:15"},
   publisher = {Leibniz International Proceedings in Informatics, LIPIcs},
   title = {Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12},
   url = {http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14},
   year = {2019}
}

TY  - JOUR
ID  - 1646176
AU  - Bokal, Drago - Dvořák, Zdeněk - Hliněný, Petr - Leanos, Jesus - Mohar, Bojan - Wiedera, Tilo
PY  - 2019
TI  - Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12
PB  - Leibniz International Proceedings in Informatics, LIPIcs
CY  - Dagstuhl
SN  - 9783959771047
KW  - Crossing number
KW  - Crossing-critical
KW  - Exhaustive generation
KW  - Path-width
UR  - http://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14
N2  - 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 Dvorák and Mohar (without an explicit construction), holds true, surprisingly, exactly for the values c <=12.
ER  -

BOKAL, Drago, Zdeněk DVOŘÁK, Petr HLINĚNÝ, Jesus LEANOS, Bojan MOHAR and Tilo WIEDERA. Bounded degree conjecture holds precisely for c-crossing-critical graphs with c\&{}lt;=12. Online. In \textit{35th International Symposium on Computational Geometry, SoCG 2019}. Dagstuhl: Leibniz International Proceedings in Informatics, LIPIcs, 2019, p.~''14:1''-''14:15'', 15 pp. ISBN~978-3-95977-104-7. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2019.14.

Detailed Information on Publication Record