Non-planar extensions of subdivisions of planar graphs

Almost 4-connectivity is a weakening of 4-connectivity which allows for vertices of degree three. In this paper we prove the following theorem. Let G be an almost 4-connected triangle-free planar graph, and let H be an almost 4-connected non-planar graph such that H has a subgraph isomorphic to a subdivision of G  . Then there exists a graph G′G′ such that G′G′ is isomorphic to a minor of H, and either(i)G′=G+uvG′=G+uv for some vertices u,v∈V(G)u,v∈V(G) such that no facial cycle of G contains both u and v, or(ii)G′=G+u1v1+u2v2G′=G+u1v1+u2v2 for some distinct vertices u1,u2,v1,v2∈V(G)u1,u2,v1,v2∈V(G) such that u1u1, u2u2, v1v1, v2v2 appear on some facial cycle of G in the order listed. This is a lemma to be used in other papers. In fact, we prove a more general theorem, where we relax the connectivity assumptions, do not assume that G   is planar, and consider subdivisions rather than minors. Instead of face boundaries we work with a collection of cycles that cover every edge twice and have pairwise connected intersection. Finally, we prove a version of this result that applies when G\XG\X is planar for some set X⊆V(G)X⊆V(G) of size at most k  , but H\YH\Y is non-planar for every set Y⊆V(H)Y⊆V(H) of size at most k.