Discrete mathematics seminar - Saturated Partial Embeddings of Planar Graphs

Speaker: Alexander Clifton (Institute for Basic Science, Korea)

Abstract: We study how far one can deviate from optimal behavior when drawing a planar graph on a plane. For a planar graph G, we say that a plane subgraph H ⊆ G is a plane-saturated subgraph if adding any edge (possibly with a new vertex) to H would either violate planarity or make the resulting graph no longer a subgraph of G. For a planar graph G, we define the plane-saturation ratio, psr(G), as the minimum value of e(H)/e(G) for a plane-saturated subgraph H ⊆ G and investigate how small psr(G) can be. While there exist planar graphs where psr(G) is arbitrarily close to 0, we show that for all twin-free planar graphs, psr(G) > 1/16, and that there exist twin-free planar graphs where psr(G) is arbitrarily close to 1/16.

Joint work with Nika Salia.