Dvorák, Zdenek ;
Hlinený, Petr ;
Mohar, Bojan
Structure and Generation of CrossingCritical Graphs
Abstract
We study ccrossingcritical graphs, which are the minimal graphs that require at least c edgecrossings when drawn in the plane. For c=1 there are only two such graphs without degree2 vertices, K_5 and K_{3,3}, but for any fixed c>1 there exist infinitely many ccrossingcritical graphs. It has been previously shown that ccrossingcritical graphs have bounded pathwidth 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 crossingcritical graphs. On the way towards this description, we prove a new structural characterisation of plane graphs of bounded pathwidth. Then we show that every ccrossingcritical graph can be obtained from a ccrossingcritical graph of bounded size by replicating boundedsize parts that already appear in narrow "bands" or "fans" in the graph. This also gives an algorithm to generate all the ccrossingcritical graphs of at most given order n in polynomial time per each generated graph.
BibTeX  Entry
@InProceedings{dvork_et_al:LIPIcs:2018:8746,
author = {Zdenek Dvor{\'a}k and Petr Hlinen{\'y} and Bojan Mohar},
title = {{Structure and Generation of CrossingCritical Graphs}},
booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)},
pages = {33:133:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770668},
ISSN = {18688969},
year = {2018},
volume = {99},
editor = {Bettina Speckmann and Csaba D. T{\'o}th},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/8746},
URN = {urn:nbn:de:0030drops87460},
doi = {10.4230/LIPIcs.SoCG.2018.33},
annote = {Keywords: crossing number, crossingcritical, pathwidth, exhaustive generation}
}
2018
Keywords: 

crossing number, crossingcritical, pathwidth, exhaustive generation 
Seminar: 

34th International Symposium on Computational Geometry (SoCG 2018)

Issue date: 

2018 
Date of publication: 

2018 