Polygon-Universal Graphs

Abstract

We study a fundamental question from graph drawing: given a pair (G, C) of a graph G and a cycle C in G together with a simple polygon P with equally many vertices as C, is there a straight-line drawing of G inside P which maps the i-th vertex of C to the i-th vertex of P ? We say that such a drawing of (G, C) respects P . We fully characterize those instances (G, C) which are polygon-universal, that is, they have a drawing that respects P for any simple (not necessarily convex) polygon P . Specifically, we identify two necessary conditions for an instance to be polygon-universal. Both conditions are based purely on graph and cycle distances and are easy to check. We show that these two conditions are also sufficient. Furthermore, if an instance (G, C) is planar, that is, if there exists a planar drawing of G with C on the outer face, we show that the same conditions guarantee for every simple polygon P the existence of a planar drawing of (G, C) that respects P . If (G, C) is polygon-universal, then our proofs directly imply a linear-time algorithm to construct a drawing that respects a given polygon P .