Structure and generation of crossing-critical graphs

D 2018

Structure and generation of crossing-critical graphs

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

Basic information

Original name

Structure and generation of crossing-critical graphs

Authors

DVOŘÁK, Zdeněk (203 Czech Republic), Petr HLINĚNÝ (203 Czech Republic, guarantor, belonging to the institution) and Bojan MOHAR (705 Slovenia)

Edition

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

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

RIV identification code

RIV/00216224:14330/18:00101458

Organization unit

Faculty of Informatics

ISBN

978-3-95977-066-8

ISSN

DOI

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

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 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.

Links

GBP202/12/G061, research and development project

Name: Centrum excelence - Institut teoretické informatiky (CE-ITI) (Acronym: CE-ITI)

Investor: Czech Science Foundation

Citovat

DVOŘÁK, Zdeněk, Petr HLINĚNÝ and 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, p. "33:1"-"33:14", 14 pp. ISBN 978-3-95977-066-8. Available from: https://dx.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 = {http://dx.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  - JOUR
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Ý and 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, p.~''33:1''-''33:14'', 14 pp. ISBN~978-3-95977-066-8. Available from: https://dx.doi.org/10.4230/LIPIcs.SoCG.2018.33.

Detailed Information on Publication Record