Structure and generation of crossing-critical graphs
| Authors | |
|---|---|
| Year of publication | 2018 |
| Type | Article in Proceedings |
| Conference | 34th International Symposium on Computational Geometry, SoCG 2018 |
| MU Faculty or unit | |
| 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: |