Nested cycles in large triangulations and crossing-critical graphs

DOI10.1016/J.JCTB.2011.04.006MaRDI QIDQ765192zbMATH OpenOpenAlexFDO

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

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

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

Abstract: We show that every sufficiently large plane triangulation has a large collection of nested cycles that either are pairwise disjoint, or pairwise intersect in exactly one vertex, or pairwise intersect in exactly two vertices. We apply this result to show that for each fixed positive integer $k$, there are only finitely many $k$-crossing-critical simple graphs of average degree at least six. Combined with the recent constructions of crossing-critical graphs given by Bokal, this settles the question of for which numbers $q>0$ there is an infinite family of $k$-crossing-critical simple graphs of average degree $q$.

Recommendations

• New infinite families of almost-planar crossing-critical graphs
• Nearly light cycles in embedded graphs and crossing-critical graphs
• Infinite families of crossing-critical graphs with prescribed average degree and crossing number
• On Degree Properties of Crossing-Critical Families of Graphs
• On degree properties of crossing-critical families of graphs

Cites work

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

Cited in

(6)

• On degree properties of crossing-critical families of graphs
• Nearly light cycles in embedded graphs and crossing-critical graphs
• Structure and generation of crossing-critical graphs
• On the achievable average degrees in 2-crossing-critical graphs
• Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\)
• scientific article; zbMATH DE number 7559214 (Why is no real title available?)

This page was built for publication: Nested cycles in large triangulations and crossing-critical graphs

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