Home | Issues | About JGAA | Instructions for Authors |
DOI: 10.7155/jgaa.00446
Column planarity and partially-simultaneous geometric embedding
Vol. 21, no. 6, pp. 983-1002, 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 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.
|
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
Seok-Hee Hong
|
Journal Supporters
|