Non-planar extensions of subdivisions of planar graphs

详细信息    查看全文

• 作者：Sergey Norin^a ; ¹ ; Robin Thomas^b ; ² ; ^{thomas@math.gatech.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Graph ; Planarity ; Non-planar extension ; Subdivision
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：121
• 期：Complete
• 页码：326-366
• 全文大小：790 K

文摘

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^{\prime }$ such that G^′$G^{\prime }$ is isomorphic to a minor of H, and either

(i)

0b36d535c" title="Click to view the MathML source">G^′=G+uv$G^{\prime }=G+uv$ for some vertices u,v∈V(G)$u,v\in V(G)$ such that no facial cycle of G contains both u and v, or

(ii)

G^′=G+u₁v₁+u₂v₂$G^{\prime }=G+u_1{v}_1+u_2{v}_2$ for some distinct vertices u₁,u₂,v₁,v₂∈V(G)$u_1,u_2,v_1,v_2\in V(G)$ such that u₁$u_1$, u₂$u_2$, v₁$v_1$, v₂$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\X$G\backslash X$ is planar for some set 90b60ef71d1835db2af" title="Click to view the MathML source">X⊆V(G)$X\subseteq V(G)$ of size at most k  , but H\Y$H\backslash Y$ is non-planar for every set Y⊆V(H)$Y\subseteq V(H)$ of size at most k.