Structure and generation of crossing-critical graphs

DOI10.4230/LIPICS.SOCG.2018.33zbMATH Open1489.68190arXiv1803.01931OpenAlexW2964213376MaRDI QIDQ5115801FDOQ5115801

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

Publication date: 18 August 2020

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.

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)

Cites Work

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

Cited In (10)

• New upper bounds for the crossing numbers of crossing-critical graphs
• On 13-crossing-critical graphs with arbitrarily large degrees
• On Degree Properties of Crossing-Critical Families of Graphs
• Structure of the set of generating graphs in the theory of pseudocriteria
• Construction of crossing-critical graphs
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• Title not available (Why is that?)
• Making a graph crossing-critical by multiplying its edges
• Title not available (Why is that?)
• 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)