Non-separating planar graphs (Q2223464)

Summary: A graph \(G\) is a non-separating planar graph if there is a drawing \(D\) of \(G\) on the plane such that (1) no two edges cross each other in \(D\) and (2) for any cycle \(C\) in \(D\), any two vertices not in \(C\) are on the same side of \(C\) in \(D\). Non-separating planar graphs are closed under taking minors and are a subclass of planar graphs and a superclass of outerplanar graphs. In this paper, we show that a graph is a non-separating planar graph if and only if it does not contain \(K_1 \cup K_4\) or \(K_1 \cup K_{2,3}\) or \(K_{1,1,3}\) as a minor. Furthermore, we provide a structural characterisation of this class of graphs. More specifically, we show that any maximal non-separating planar graph is either an outerplanar graph or a wheel or it is a graph obtained from the disjoint union of two triangles by adding three vertex-disjoint paths between the two triangles. Lastly, to demonstrate an application of non-separating planar graphs, we use the characterisation of non-separating planar graphs to prove that there are maximal linkless graphs with \(3n-3\) edges. Thus, maximal linkless graphs can have significantly fewer edges than maximum linkless graphs; \textit{H. Sachs} [Lect. Notes Math. 1018, 230--241 (1983; Zbl 0525.05024)] exhibited linkless graphs with \(n\) vertices and \(4n-10\) edges (the maximum possible).