Information Technology Reference
In-Depth Information
Column Planarity and Partial Simultaneous
Geometric Embedding
William Evans
1
, Vincent Kusters
2
, Maria Saumell
3
, and Bettina Speckmann
4
1
University of British Columbia, Canada
will@cs.ubc.ca
2
Department of Computer Science, ETH Zurich, Switzerland
vincent.kusters@inf.ethz.ch
3
Department of Mathematics and European Centre of Excellence NTIS,
University of West Bohemia, Czech Republic
saumell@kma.zcu.cz
4
Technical University Eindhoven, The Netherlands
b.speckmann@tue.nl
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 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 suciently large
n
,thereexistsan
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.
1 Introduction
Agraph
G
=(
V,E
)on
n
vertices is
unlabeled level planar (ULP)
if for all
injections
ʳ
:
V ₒ
R
, there exists an injection
ˁ
:
V ₒ
R
,sothatembed-
ding each
v ∈ V
at (
ˁ
(
v
)
,ʳ
(
v
)) results in a plane straight-line embedding of
W. Evans is supported by an NSERC Discovery Grant. V. Kusters is partially sup-
ported by the ESF EUROCORES programme EuroGIGA, CRP GraDR and the
Swiss National Science Foundation, SNF Project 20GG21-134306. M. Saumell is
supported by the project NEXLIZ CZ.1.07/2.3.00/30.0038, which is co-financed by
the European Social Fund and the state budget of the Czech Republic. B. Speck-
mann is supported by the Netherlands Organisation for Scientific Research (NWO)
under project no. 639.023.208.
