Nested cycles in large triangulations and crossing-critical graphs

DOI10.1016/j.jctb.2011.04.006zbMath1237.05113arXiv0911.4690OpenAlexW2000808638MaRDI QIDQ765192

Robin Thomas, César Hernández-Vélez, Gelasio Salazar

Publication date: 19 March 2012

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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

zbMATH Keywords

triangulationscrossing numberscrossing-criticalnested cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10)

Related Items

Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\), On degree properties of crossing-critical families of graphs, Unnamed Item, Structure and generation of crossing-critical graphs

Cites Work

• Graph minors. XX: Wagner's conjecture
• Infinite families of crossing-critical graphs with a given crossing number
• Graph minors. III. Planar tree-width
• Typical subgraphs of 3- and 4-connected graphs
• Minimal graphs with crossing number at least \(k\)
• Crossing-critical graphs with large maximum degree
• Graph minors. VI. Disjoint paths across a disc
• Construction of crossing-critical graphs
• Crossing-number critical graphs have bounded path-width
• Infinite families of crossing-critical graphs with given average degree
• On the decay of crossing numbers
• Graph minors. IV: Tree-width and well-quasi-ordering
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• Stars and bonds in crossing-critical graphs
• Planar Separators
• Crossing numbers of sequences of graphs II: Planar tiles
• Improvement on the Decay of Crossing Numbers