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.

Základní údaje

Originální název

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

Autoři

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ ; Jesus LEANOS; Bojan MOHAR a Tilo WIEDERA

Vydání

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

Nakladatel

Leibniz International Proceedings in Informatics, LIPIcs

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Spojené státy

Utajení

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

Forma vydání

elektronická verze "online"

Odkazy

open access

Kód RIV

RIV/00216224:14330/19:00108275

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-104-7

ISSN

DOI

https://doi.org/10.4230/LIPIcs.SoCG.2019.14

EID Scopus

2-s2.0-85068041340

Klíčová slova anglicky

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

Štítky

core_A, firank_A, formela-conference

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 14. 6. 2022 12:11, RNDr. Pavel Šmerk, Ph.D.

Anotace

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.

Návaznosti

GA17-00837S, projekt VaV

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

Investor: Grantová agentura ČR, Structural properties, parameterized tractability and hardness in combinatorial problems

Citovat

BOKAL, Drago; Zdeněk DVOŘÁK; Petr HLINĚNÝ; Jesus LEANOS; Bojan MOHAR a 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, s. "14:1"-"14:15", 15 s. ISBN 978-3-95977-104-7. Dostupné z: https://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 = {https://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  - CONF
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 a 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, s.~''14:1''-''14:15'', 15 s. ISBN~978-3-95977-104-7. Dostupné z: https://doi.org/10.4230/LIPIcs.SoCG.2019.14.

Přehled o publikaci