Structure and generation of crossing-critical graphs

D 2018

Structure and generation of crossing-critical graphs

DVOŘÁK, Zdeněk; Petr HLINĚNÝ a Bojan MOHAR

Základní údaje

Originální název

Structure and generation of crossing-critical graphs

Autoři

DVOŘÁK, Zdeněk; Petr HLINĚNÝ a Bojan MOHAR

Vydání

Dagstuhl, 34th International Symposium on Computational Geometry, SoCG 2018, od s. "33:1"-"33:14", 14 s. 2018

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"

Označené pro přenos do RIV

Ano

Kód RIV

RIV/00216224:14330/18:00101458

Organizační jednotka

Fakulta informatiky

ISBN

978-3-95977-066-8

ISSN

DOI

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

EID Scopus

2-s2.0-85048958080

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 c = 1 there are only two such graphs without degree-2 vertices, K5 and K3,3, but for any fixed c > 1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.

Návaznosti

GBP202/12/G061, projekt VaV

Název: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Akronym: CE-ITI)

Investor: Grantová agentura ČR, Centrum excelence - Institut teoretické informatiky

Citovat

DVOŘÁK, Zdeněk; Petr HLINĚNÝ a Bojan MOHAR. Structure and generation of crossing-critical graphs. Online. In 34th International Symposium on Computational Geometry, SoCG 2018. Dagstuhl: Leibniz International Proceedings in Informatics, LIPIcs, 2018, s. "33:1"-"33:14", 14 s. ISBN 978-3-95977-066-8. Dostupné z: https://doi.org/10.4230/LIPIcs.SoCG.2018.33.

@inproceedings{1480303,
   author = {Dvořák, Zdeněk and Hliněný, Petr and Mohar, Bojan},
   address = {Dagstuhl},
   booktitle = {34th International Symposium on Computational Geometry, SoCG 2018},
   doi = {https://doi.org/10.4230/LIPIcs.SoCG.2018.33},
   keywords = {Crossing number; Crossing-critical; Exhaustive generation; Path-width},
   howpublished = {elektronická verze "online"},
   language = {eng},
   location = {Dagstuhl},
   isbn = {978-3-95977-066-8},
   pages = {"33:1"-"33:14"},
   publisher = {Leibniz International Proceedings in Informatics, LIPIcs},
   title = {Structure and generation of crossing-critical graphs},
   year = {2018}
}

TY  - CONF
ID  - 1480303
AU  - Dvořák, Zdeněk - Hliněný, Petr - Mohar, Bojan
PY  - 2018
TI  - Structure and generation of crossing-critical graphs
PB  - Leibniz International Proceedings in Informatics, LIPIcs
CY  - Dagstuhl
SN  - 9783959770668
KW  - Crossing number
KW  - Crossing-critical
KW  - Exhaustive generation
KW  - Path-width
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 c = 1 there are only two such graphs without degree-2 vertices, K5 and K3,3, but for any fixed c > 1 there exist infinitely many c-crossing-critical graphs. It has been previously shown that c-crossing-critical graphs have bounded path-width and contain only a bounded number of internally disjoint paths between any two vertices. We expand on these results, providing a more detailed description of the structure of crossing-critical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded path-width. Then we show that every c-crossing-critical graph can be obtained from a c-crossing-critical graph of bounded size by replicating bounded-size parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the c-crossing-critical graphs of at most given order n in polynomial time per each generated graph.
ER  -

DVOŘÁK, Zdeněk; Petr HLINĚNÝ a Bojan MOHAR. Structure and generation of crossing-critical graphs. Online. In \textit{34th International Symposium on Computational Geometry, SoCG 2018}. Dagstuhl: Leibniz International Proceedings in Informatics, LIPIcs, 2018, s.~''33:1''-''33:14'', 14 s. ISBN~978-3-95977-066-8. Dostupné z: https://doi.org/10.4230/LIPIcs.SoCG.2018.33.

Přehled o publikaci