Nested cycles in large triangulations and crossing-critical graphs

DOI10.1016/J.JCTB.2011.04.006zbMATH Open1237.05113arXiv0911.4690OpenAlexW2000808638MaRDI QIDQ765192FDOQ765192

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)

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$.

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)

Cites Work

• Graph minors. XX: Wagner's conjecture
• Typical subgraphs of 3- and 4-connected graphs
• Graph minors. III. Planar tree-width
• Graph minors. VI. Disjoint paths across a disc
• Planar Separators
• Graph minors. IV: Tree-width and well-quasi-ordering
• 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
• 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
• Improvement on the Decay of Crossing Numbers
• Infinite families of crossing-critical graphs with a given crossing number
• Minimal graphs with crossing number at least \(k\)
• Crossing-critical graphs with large maximum degree

Cited In (5)

• On degree properties of crossing-critical families of 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\)
• Title not available (Why is that?)

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)