Home  Issues  Aims and Scope  Instructions for Authors 
DOI: 10.7155/jgaa.00446
Column planarity and partiallysimultaneous geometric embedding
Vol. 21, no. 6, pp. 9831002, 2017. Regular paper.
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 straightline 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 partiallysimultaneous 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.

Submitted: December 2015.
Reviewed: May 2016.
Revised: September 2016.
Reviewed: November 2016.
Revised: May 2017.
Accepted: July 2017.
Final: September 2017.
Published: October 2017.
Communicated by
SeokHee Hong
