Maximal planar graphs that embed as centers

Abstract

A maximal planar graph is a graph which can be embedded in the plane such that every face of the graph is a triangle. The center of a graph is the subgraph induced by the vertices of minimum eccentricity. We introduce the notion of quasi-eccentric vertices, and use this to characterize maximal planar graphs that are the center of some planar graph. We also present some easier to check only necessary / only sufficient conditions for planar and maximal planar graphs to be the center of a planar graph. Finally, we use the aforementioned characterization to prove that all maximal planar graphs of order at most 8 are the center of some planar graph -- and this bound is sharp.

24 pages, 18 figures. An early version of this work appeared in the Author's thesis "Distances in Planar Graphs", available on the UCT open thesis repository (2021)