Ding, Guoli; Oporowski, Bogdan; Thomas, Robin; Vertigan, Dirk Large non-planar graphs and an application to crossing-critical graphs. (English) Zbl 1223.05153 J. Comb. Theory, Ser. B 101, No. 2, 111-121 (2011). 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. Reviewer: Michael Hager (Leonberg) Cited in 7 Documents MSC: 05C40 Connectivity 05C83 Graph minors 05C12 Distance in graphs 05C35 Extremal problems in graph theory Keywords:graph minors PDFBibTeX XMLCite \textit{G. Ding} et al., J. Comb. Theory, Ser. B 101, No. 2, 111--121 (2011; Zbl 1223.05153) Full Text: DOI arXiv References: [1] D. Bokal, R.B. Richter, G. Salazar, Characterization of 2-crossing-critical graphs I: Low connectivity or no \(V_{2 n}\); D. Bokal, R.B. Richter, G. Salazar, Characterization of 2-crossing-critical graphs I: Low connectivity or no \(V_{2 n}\) [2] G. Ding, B. Oporowski, R. Thomas, D. Vertigan, Large 4-connected nonplanar graphs, manuscript, August 1999.; G. Ding, B. Oporowski, R. Thomas, D. Vertigan, Large 4-connected nonplanar graphs, manuscript, August 1999. [3] Mohar, B.; Thomassen, C., Graphs on Surfaces (2001), Johns Hopkins University Press: Johns Hopkins University Press Baltimore, MD · Zbl 0979.05002 [4] Oporowski, B.; Oxley, J.; Thomas, R., Typical subgraphs of 3- and 4-connected graphs, J. Combin. Theory Ser. B, 57, 239-257 (1993) · Zbl 0728.05041 [5] Robertson, N.; Seymour, P. D., Graph minors IX. Disjoint crossed paths, J. Combin. Theory Ser. B, 49, 40-77 (1990) · Zbl 0741.05044 [6] N. Robertson, P.D. Seymour, R. Thomas, Non-planar extensions of planar graphs, manuscript.; N. Robertson, P.D. Seymour, R. Thomas, Non-planar extensions of planar graphs, manuscript. This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.