2014 | OriginalPaper | Buchkapitel
Column Planarity and Partial Simultaneous Geometric Embedding
verfasst von : William Evans, Vincent Kusters, Maria Saumell, Bettina Speckmann
Erschienen in: Graph Drawing
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 column planar subsets of trees: any tree on
n
vertices contains a column planar set of size at least 14
n
/17 and for any
ε
> 0 and any sufficiently large
n
, there exists an
n
-vertex tree in which every column planar subset has size at most (5/6 +
ε
)
n
.
We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partial SGE (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 in which
k
vertices are still mapped to the same point. In particular, we show that any two trees on
n
vertices admit an 11
n
/17-PSGE, two outerpaths admit an
n
/4-PSGE, and an outerpath and a tree admit a 11
n
/34-PSGE.