TY - JOUR

T1 - Non-separating planar graphs

AU - Dehkordi, Hooman R.

AU - Farr, Graham

N1 - Publisher Copyright:
© 2021, Australian National University. All rights reserved.

PY - 2021/1/15

Y1 - 2021/1/15

N2 - 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 K1 ∪ K4 or K1 ∪ K2,3 or K1,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; Sachs exhibited linkless graphs with n vertices and 4n − 10 edges (the maximum possible) in 1983.

AB - 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 K1 ∪ K4 or K1 ∪ K2,3 or K1,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; Sachs exhibited linkless graphs with n vertices and 4n − 10 edges (the maximum possible) in 1983.

UR - http://www.scopus.com/inward/record.url?scp=85100219812&partnerID=8YFLogxK

U2 - 10.37236/8816

DO - 10.37236/8816

M3 - Article

AN - SCOPUS:85100219812

SN - 1077-8926

VL - 28

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 1

M1 - P1.11

ER -