Bounded degree conjecture holds precisely for c-crossing-critical graphs with c 12

DOI10.4230/LIPICS.SOCG.2019.14MaRDI QIDQ5088941zbMATH OpenFDO

Authors Drago Bokal, Zdeněk Dvořák, Petr Hliněný, Bojan Mohar, Tilo Wiedera, J. Leaños

Publication date 18 July 2022

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

zbMATH Keywords

graph drawingcrossing numbercrossing-criticalzip product

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• Crossing-critical graphs with large maximum degree
• New upper bounds for the crossing numbers of crossing-critical graphs
• Stars and Bonds in Crossing-Critical Graphs

Cites work

• An ILP-based Proof System for the Crossing Number Problem
• Characterizing 2-crossing-critical graphs
• Construction of crossing-critical graphs
• Crossing number additivity over edge cuts
• Crossing-Free Subgraphs
• Crossing-critical graphs with large maximum degree
• Crossing-number critical graphs have bounded path-width
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Nested cycles in large triangulations and crossing-critical graphs
• ON THE ADDITIVITY OF CROSSING NUMBERS OF GRAPHS
• On degree properties of crossing-critical families of graphs
• Research problems from the 5th Slovenian Conference (Bled, 2003)
• Structure and generation of crossing-critical graphs

Cited in

(6)

• Properties of large 2-crossing-critical graphs
• On 13-crossing-critical graphs with arbitrarily large degrees
• On the achievable average degrees in 2-crossing-critical graphs
• Domination and independence number of large 2-crossing-critical graphs
• Improvement on the Crossing Number of Crossing-Critical Graphs
• Improvement on the crossing number of crossing-critical graphs

This page was built for publication: Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c\le 12\)

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