Large non-planar graphs and an application to crossing-critical graphs (Q631645)

The authors 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. They 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.