Information Technology Reference
In-Depth Information
c
f
b
f
a
e
e
d
f
a
a
d
b
e
d
b
c
c
1234 1234
(a)
(b)
(c)
Fig. 1.
(a) A graph
G
=(
V,E
)with
R
=
{a,d,e,f}
which is
ˁ
-column planar for
ˁ
=
{d ₒ
1
,a ₒ
2
,e ₒ
3
,f ₒ
4
}
. (b-c) Two assignments of
y
-coordinates to the
vertices
R
and corresponding plane straight-line completions of
G
.
G
. Estrella-Balderrama, Fowler and Kobourov [10] originally introduced ULP
graphs and characterized ULP trees in terms of forbidden subgraphs. Fowler
and Kobourov [12] extended this characterization to general ULP graphs. ULP
graphs are exactly the graphs that admit a simultaneous geometric embedding
with a monotone path: this was the original motivation for studying them.
In this paper we introduce the notion of
column planarity
of a subset
R
of the
vertices
V
of a graph
G
=(
V,E
). 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. It is a relaxation since it applies only
toasubset
R
of the vertices and a strengthening since the requirements on
R
are more strict than in the case of unlabeled level planarity.
More formally, for
R
V
,wesaythat
R
is
column planar in G
=(
V,E
)
if there exists an injection
ˁ
:
R
ↆ
ₒ
R
such that for all
ˁ-compatible
injections
ʳ
:
R
R
is embedded at (
ˁ
(
v
)
,ʳ
(
v
)). Injection
ʳ
is
ˁ
-compatible if the combination of
ˁ
and
ʳ
does not embed three vertices on a line. Clearly, if
R
is column planar in
G
then any subset of
R
is also column planar in
G
.Wesaythat
R
is
ˁ-column
planar
when we need to emphasize the injection
ˁ
(see Fig. 1 for an example).
If
R
=
V
is column planar in
G
then
G
is ULP since column planarity implies
the existence of one assignment of
x
-coordinates to vertices that will produce a
planar embedding for all assignments of
y
-coordinates, while to be a ULP graph
the
x
-coordinate assignment may depend on the
y
-coordinate assignment. In
this sense, column planarity of
V
is strictly more restrictive than unlabeled level
planarity of
G
. Di Giacomo et al. [8] study column planarity under a different
name. Specifically, they define EAP graphs as the graphs
G
=(
V,E
)where
V
is column planar in
G
. They consider a family of graphs called
fat caterpillars
and prove that these are exactly the EAP graphs.
As mentioned above, the study of ULP was originally motivated by simulta-
neous geometric embedding, a concept introduced by Brass et al. [4]. Formally,
given two graphs
G
1
=(
V,E
1
)and
G
2
=(
V,E
2
) on the same set of
n
vertices,
they defined a
simultaneous geometric embedding (SGE)
of
G
1
and
G
2
as an
ₒ
R
, there exists a plane straight-line embedding of
G
where each
v
∈
