Structure and generation of crossing-critical graphs

DOI10.4230/LIPICS.SOCG.2018.33MaRDI QIDQ5115801zbMATHOpenAlexFDO

Authors Zdeněk Dvořák, Petr Hliněný, Bojan Mohar

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1803.01931

zbMATH Keywords

path-widthexhaustive generationcrossing numbercrossing-critical

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Abstract: 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, K_5 and K_3,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.

Recommendations

• Properties of large 2-crossing-critical graphs
• scientific article; zbMATH DE number 2084270
• Crossing-number critical graphs have bounded path-width
• Stars and Bonds in Crossing-Critical Graphs
• New infinite families of almost-planar crossing-critical graphs

Cites work

• scientific article; zbMATH DE number 2084270 (Why is no real title available?)
• Characterizing 2-crossing-critical graphs
• Construction of crossing-critical graphs
• Crossing Numbers and Hard Erdős Problems in Discrete Geometry
• Crossing number is hard for kernelization
• Crossing numbers of sequences of graphs II: Planar tiles
• Crossing-Free Subgraphs
• Crossing-critical graphs with large maximum degree
• Crossing-number critical graphs have bounded path-width
• Factorization forests for infinite words and applications to countable scattered linear orderings
• Factorization forests of finite height
• Graphs on surfaces
• Infinite families of crossing-critical graphs with a given crossing number
• Infinite families of crossing-critical graphs with given average degree
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Nested cycles in large triangulations and crossing-critical graphs
• Stars and bonds in crossing-critical graphs

Cited in

(10)

• Making a graph crossing-critical by multiplying its edges
• Structure of the set of generating graphs in the theory of pseudocriteria
• On 13-crossing-critical graphs with arbitrarily large degrees
• On Degree Properties of Crossing-Critical Families of Graphs
• Construction of crossing-critical graphs
• scientific article; zbMATH DE number 2084270 (Why is no real title available?)
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• New upper bounds for the crossing numbers of crossing-critical graphs
• scientific article; zbMATH DE number 7559214 (Why is no real title available?)
• Properties of large 2-crossing-critical graphs

This page was built for publication: Structure and generation of crossing-critical graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115801)