Publication details

Structure and generation of crossing-critical graphs

Authors

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

Year of publication 2018
Type Article in Proceedings
Conference 34th International Symposium on Computational Geometry, SoCG 2018
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.4230/LIPIcs.SoCG.2018.33
Keywords Crossing number; Crossing-critical; Exhaustive generation; Path-width
Description 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.
Related projects: