Information Technology Reference
In-Depth Information
EAPgraphs makes it possible to extend several results aboutSGEpreviously described
in the literature, thanks to the following result (see also Theorem 2 and Corollary 2).
G
1
,G
2
be a pair of graphssuch that
G
1
∈
AEP
and
G
2
∈
EAP
.
Theorem 1.
Let
G
1
,G
2
Then
admits aSGE.
Proof.
Since
G
2
is an EAPgraph, there exists a universal
y
-leveling
Y
of
G
2
. Consider
Y
as a
y
-leveling of
G
1
; we aim at finding an
x
-leveling
X
of
G
1
that is general with
respect to
Y
and such that
ʓ
(
X
,
Y
) is planar. Since
G
1
∈
AEP
, then there exists an
X
X
,
X
x
-leveling
such that
ʓ
1
(
Y
) is a planar drawing of
G
1
.If
is general with
X
;if
X
is not general with respect to
respect to
Y
we set
X
=
Y
, then, by Lemma 1,
X
that is general with respect to
X
,
there exists an
x
-leveling
Y
and such that
ʓ
(
Y
)
X
. In either case we have the desired
x
-leveling
is planar; in this case we set
X
=
X
.
Consider
X
as an
x
-leveling for
G
2
.Then
ʓ
2
(
X
,
Y
) is a planar drawing of
G
2
because
G
2
is an EAPgraph,
Y
is a universal
y
-leveling of
G
2
and
X
is general with respect to
Y
.Thus,
ʓ
1
(
X
,
Y
)
,ʓ
2
(
X
,
Y
)
is a SGE of
G
1
,G
2
.
Characterization of EAP graphs.
AEPgraphs have been characterized by Fowler and
Kobourov [11]. We first show that EAPgraphs constitute a subfamily of AEPgraphs
with stronger properties (Lemma 3) and then we characterize EAPgraphs (Theorem 2).
Lemma 3.
Let
G
∈
EAP
.Then
G
∈
AEP
.
Proof.
Let
Y
be an arbitrary given
y
-leveling of
G
. In order to prove that
G
∈
AEP
we
X
such that
ʓ
(
X
,
Y
) is a planar drawing.
must show that there exists an
x
-leveling
Since
G
is an EAPgraph, there exists a universal
y
-leveling
Y
of
G
. We define an
x
-
Y
. In other words we assign to each vertex
v
an
x
-coordinate
leveling
X
for
G
as
X
=
Y
(
v
) assigned to
v
by
Y
. We have two cases:
X
(
v
) that is equal to the
y
-coordinate
Case 1:
X
is general with respect to
Y
. In this case, since
G
∈
EAP
,
ʓ
(
X
,
Y
) is a
X
=
X
,
Y
) is the drawing
ʓ
(
planar drawing.Ifweset
Y
,wehavethat
ʓ
(
X
,
Y
)
rotated by 90
ⓦ
and hence it is planar.
Case 2:
Y
X
is not general with respect to
Y
.ByLemma2thereexistsa
y
-leveling
Y
)) =
X
be
that is general with respect to
X
such that
ihs
(
ʓ
(
X
,
ihs
(
ʓ
(
X
,
Y
)).Let
an
x
-leveling that is general with respect to
Y
ihs
(
ʓ
(
X
,
Y
ihs
(
ʓ
(
X
,
Y
;wehave
)) =
))
because
ʓ
(
X
,
Y
) and
ʓ
(
X
,
Y
) have the same
y
-leveling.Since
G
is an EAPgraph,
ihs
Y
) is
planar (otherwise its independent horizontal stabbing number would be at least two). If
we set
(
ʓ
(
X
,
Y
ihs
(
ʓ
(
X
,
Y
)) = 1, which implies that
ʓ
(
X
,
)) = 1 and hence
X
=
Y
then
ʓ
(
X
,Y
) is
ʓ
(
X,Y
) rotated by 90
ⓦ
, and hence is planar.
In both cases we have found an
x
-leveling
X
such that
ʓ
(
X
,
Y
) is a planar draw-
Y
is arbitrary, we have that
G
ing.Since
∈
AEP
.
AEP
. By the characterization of Fowler and
Kobourov [11] we know precisely the graphs in
AEP
; therefore in order to character-
ize the class
EAP
we can establish which graphs of the set
AEP
are EAPgraphs. The
family of AEPgraphs is the union of the following three families:
radius-2 stars
,
ex-
tended degree-3 spiders
,and
generalized caterpillars
. In order to recall the definition of
these families we start by defining four gadgets each having two vertices called
poles
.
By Lemma 3 we have that
EAP
ↆ
