Large non-planar graphs and an application to crossing-critical graphs

DOI10.1016/J.JCTB.2010.12.001MaRDI QIDQ631645zbMATH OpenOpenAlexFDO

Authors Guoli Ding, Bogdan Oporowski, Robin Thomas, Dirk Vertigan

Publication date 14 March 2011

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

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

zbMATH Keywords

graph minors

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Distance in graphs (05C12) Connectivity (05C40) Graph minors (05C83)

Abstract: We prove that, for every positive integer k, there is an integer N such that every 4-connected non-planar graph with at least N vertices has a minor isomorphic to K_{4,k}, the graph obtained from a cycle of length 2k+1 by adding an edge joining every pair of vertices at distance exactly k, or the graph obtained from a cycle of length k by adding two vertices adjacent to each other and to every vertex on the cycle. We also prove a version of this for subdivisions rather than minors, and relax the connectivity to allow 3-cuts with one side planar and of bounded size. We deduce that for every integer k there are only finitely many 3-connected 2-crossing-critical graphs with no subdivision isomorphic to the graph obtained from a cycle of length 2k by joining all pairs of diagonally opposite vertices.

Recommendations

• Characterizing 2-crossing-critical graphs
• Characterizing graphs with crossing number at least 2
• Stars and Bonds in Crossing-Critical Graphs
• Minors in large almost-5-connected non-planar graphs
• Properties of large 2-crossing-critical graphs

Cites work

• Graph minors. IX: Disjoint crossed paths
• Graphs on surfaces
• Typical subgraphs of 3- and 4-connected graphs

Cited in

(9)

• Characterizing 2-crossing-critical graphs
• Non-embeddable extensions of embedded minors
• Graphs with at most one crossing
• On the decay of crossing numbers of sparse graphs
• Characterizing graphs with crossing number at least 2
• Crossing-number critical graphs have bounded path-width
• Minors in large almost-5-connected non-planar graphs
• Domination and independence number of large 2-crossing-critical graphs
• Non-planar extensions of subdivisions of planar graphs

This page was built for publication: Large non-planar graphs and an application to crossing-critical graphs

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