Column planarity and partially-simultaneous geometric embedding

Abstract

We introduce the notion of column planarity of a subset $R$ of the vertices of a graph $G$. Informally, we say that $R$ is column planar in $G$ if we can assign $x$-coordinates to the vertices in $R$ such that any assignment of $y$-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of $G$. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for the maximum size of column planar subsets of trees: every tree on $n$ vertices contains a column planar set of size at least $14n/17$ and for any $\epsilon > 0$ and any sufficiently large $n$, there exists an $n$-vertex tree in which every column planar subset has size at most $(5/6 + \epsilon)n$. In addition, we show that every outerplanar graph has a column planar set of size at least $n/2$. We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partially-simultaneous geometric embedding (PSGE). A PSGE of two graphs $G_1$ and $G_2$ allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct $k$-PSGEs, which are PSGEs in which at least $k$ vertices are mapped to the same point for both graphs. In particular, we show that every two trees on $n$ vertices admit an $11n/17$-PSGE and every two outerplanar graphs admit an $n/4$-PSGE.