Saturated Partial Embeddings of Planar Graphs

ABSTRACT

In this work, we study how far one can deviate from optimal behavior when embedding a planar graph. For a planar graph , we say that a plane subgraph is a plane‐saturated subgraph if adding any edge (possibly with new vertices) to would either violate planarity or make the resulting graph no longer a subgraph of . For a planar graph , we define the plane‐saturation ratio , , as the minimum value of for a plane‐saturated subgraph of and investigate how small can be. While there exist planar graphs where is arbitrarily close to 0, we show that for all twin‐free planar graphs, , and that there exist twin‐free planar graphs where is arbitrarily close to 1/16. We study a broader category of planar graphs, focusing on classes characterized by a bounded number of degree 1 and degree 2 twin vertices. We offer solutions for some instances of bounds while positing conjectures for the remaining ones.