2009/11/24 by César Hernández-Vélez, Cesar Hernandez-Velez, Gelasio Salazar +1 · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Degree (music) #Discrete mathematics #Disjoint sets #Geometry #Graph #Integer (computer science) #Limits and Structures in Graph Theory #Mathematics #Pairwise comparison #Physics #Simple (philosophy) #Statistics #Triangulation #Vertex (graph theory) #math.CO #msc:05C10
paper · pdf · doi:10.1016/j.jctb.2011.04.006
published in Journal of Combinatorial Theory Series B 102(1), 86-92 (Elsevier BV)
arxiv created 2009/11/24 · openalex publication_date 2011/07/06 · arxiv updated 2019/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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.