Other formats:
BibTeX
LaTeX
RIS
@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.
|
