Non-planar extensions of subdivisions of planar graphs

Abstract

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'$ such that $G'$ is isomorphic to a minor of $H$, and either (i) $G'=G+uv$ for some vertices $u,v\in V(G)$ such that no facial cycle of $G$ contains both $u$ and $v$, or (ii) $G'=G+u_1v_1+u_2v_2$ for some distinct vertices $u_1,u_2,v_1,v_2\in V(G)$ such that $u_1,u_2,v_1,v_2$ 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\backslash X$ is planar for some set $X\subseteq V(G)$ of size at most $k$, but $H\backslash Y$ is non-planar for every set $Y\subseteq V(H)$ of size at most $k$.

This version fixes an error in the published paper. The error was kindly pointed out to us by Katherine Naismith. Changes from the published version are indicated in red. 57 pages, 8 figures