Information Technology Reference
In-Depth Information
0
,
1
,...,
h
be a set of half-lines each having initial point (0
,
0) and all extending in
the upper half-plane, ordered as they are encountered rotating clockwise starting at the
negative
x
-axis. Let
C
i
be the cone delimited by
i−
1
and
i
. In order to obtain a planar
drawing of a star it is sufficient to map its vertices to a set of points in general position,
i.e., a set of points such that there are no three collinear points. So in order to draw
G
1
we can map the vertices of each
S
i
(
i
=1
,
2
,...,h
) to points in general position
of a different cone
C
j
and the root of
G
1
to point (0
,
0) shared by all regions. In this
way each star
S
i
is drawn planarly inside a different
C
j
(thus different stars do not cross
each other) and the root vertex can be connected without crossings to its adjacent vertex
of each star
S
i
(see Fig. 3(c)). It can be shown that
G
2
admits a drawing such that the
vertex corresponding to the root of
G
1
is mapped to (0
,
0) and the points corresponding
to each star
S
i
are mapped to a different cone
C
j
(see Fig.3(d)).
4
Simultaneous Geometric Quasi Planar Embeddings
We introduce and study geometric simultaneous embeddings where each of the two
drawings are not required to be planar but only quasi planar. We implicitly assume that
all drawings are straight-lines. Let
G
be a graph and let
ʓ
beadrawing of
G
.
ʓ
is
quasi
planar
if there are no three mutually crossing edges. A graph is
quasi planar
if it admits
aquasi planar drawing.Let
beapairofquasi planar
graphs with the same vertex set. A
simultaneous geometric quasi planarembedding
(
SGQPE
)of
G
1
=(
V,E
1
)
,G
2
=(
V,E
2
)
such that: (
i
)
ʓ
i
is a quasi planar
straight-line drawing of
G
i
for
i
=1
,
2; (
ii
) each vertex
v
G
1
,G
2
ʓ
1
,ʓ
2
isapairofdrawings
V
is represented by the
same point in
ʓ
1
and
ʓ
2
. We extend the definition of AEP and EAPgraphs to the quasi
planar case as follows. A quasi planar graph
G
is an
AEQPgraph
if for any
y
-leveling
Y
∈
of
G
, there exists an
x
-leveling
X
such that
ʓ
(
X
,
Y
) is quasi planar.
G
is an
EAQP
graph
if there exists a
y
-leveling
Y
of
G
, called a
universalquasi planarleveling
,such
that for any
x
-leveling
) is quasi planar.
Denote by
AEQP
and
EAQP
the set of AEQP and EAQPgraphs, respectively. The
next result generalizes Theorem 1.
X
that is general with respect to
Y
,
ʓ
(
X
,
Y
Theorem 4.
Let
G
1
,G
2
be a pair of graphssuch that
G
1
∈
AEQP
and
G
2
∈
EAQP
.Then
G
1
,G
2
admits aSGQPE.
Motivated by Theorem 4 we study the interplay between AEQP and EAQPgraphs
and also their relationships with AEP and EAPgraphs, which are summarized by Fig.4
and Theorem 6. We first show that any AEPgraph is an EAQPgraph (Lemma 7). The
next technical lemma generalizes Lemma 4 (the proof is similar).
Lemma 6.
A graph
G
is an EAQPgraph if andonly if
ihs
(
G
)
≤
2
.
Lemma 7.
AEP
ↂ
EAQP
.
Sketch of Proof:
Let
G
be an
AEP
graph; it is either a radius-2 star, or a generalized
degree-3 spider, or a generalized caterpillar. For each type of graph we describe a
y
-
leveling that is universal quasi planar. The proof of correctness is omitted.
