Information Technology Reference
In-Depth Information
such that: (
i
)
ʓ
i
is a planar straight-line drawing of
G
i
for
i
=1
,
2; (
ii
) each vertex
v
∈
V
is represented by the same point in
ʓ
1
and
ʓ
2
.
Let
G
beaplanargraph. An
x
-leveling
of
G
is a mapping
X
:
V
ₒ
R
that assigns to
each vertex of
G
a distinct real
x
-coordinate. A
y
-leveling
of
G
is a mapping
ₒ
R
that assigns to each vertex of
G
a distinct real
y
-coordinate. Let
G
be a planar graph
with a given
x
-leveling
Y
:
V
X
and a given
y
-leveling
Y
. We denote by
ʓ
(
X
,
Y
) astraight-
line drawing of
G
obtained by drawing each vertex
v
at point (
X
(
v
)
,
Y
(
v
)) and each
edgeasastraight-line segment between its endpoints. If
ʓ
(
X
,
Y
) has no three collinear
vertices we say that
.
Let
G
be a graph and let
ʓ
be a straight-line drawing of
G
.Twoedges of
G
are
independent
if they do not have an endvertex in common. The
independent horizon-
talstabbing number
of
ʓ
, denoted by
X
is
general with respect to
Y
,and
Y
is
general with respect to
X
(
ʓ
), is the maximumnumber of independent
edges of
ʓ
intersected by a horizontal line. The
independent horizontalstabbing num-
ber
of
G
, denoted by
ihs
(
G
), is the minimum independent horizontal stabbing number
over all straight-line drawingsof
G
. A horizontal line is called a
stabber
; the stabber of
equation
y
=
l
is the
stabber at
l
.Twodrawings with the same top-to-bottom order of
the vertices have the same independent horizontal stabbing number. The next lemmas
are used to remove collinear points in a drawing.
ihs
Lemma 1.
Let
G
be agraph.Let
Y
be a
y
-leveling of
G
andlet
X
be an
x
-leveling of
G
thatisnot general with respect to
Y
.There exists an
x
-leveling
X
thatisgeneral with
X
,
respect to
Y
andsuch thatiftwoedges cross in
ʓ
(
Y
)
then they cross in
ʓ
(
X
,
Y
)
.
Lemma 2.
Let
G
be agraph.Let
Y
be a
y
-leveling of
G
andlet
X
be an
x
-leveling of
Y
thatisgeneral with
G
thatisnot general with respect to
Y
.There exists a
y
-leveling
Y
)) =
respect to
X
andsuch that
ihs
(
ʓ
(
X
,
ihs
(
ʓ
(
X
,
Y
))
.
3
EAP Graphs and Simultaneous Geometric Embedding
Before defining EAPgraphs, we recall the definition of ULPgraphs (introduced in [11]),
which we rename as
AEPgraphs
.Let
G
be a planar graph.
G
is an
AEPgraph
if for any
y
-leveling
Y
of
G
, there exists an
x
-leveling
X
such that
ʓ
(
X,Y
) is planar.
G
is an
EAP
graph
if there exists a
y
-leveling
Y
of
G
, called
universal
y
-leveling
,such that for any
) is planar
2
. We denote by
AEP
the set of AEPgraphs and by
EAP
the set of EAPgraphs. Note that, in the definition of
EAPgraphs we consider only
x
-levelingsthataregeneral with respect to the
y
-leveling
Y
x
-leveling
X
that is general with respect to
Y
,
ʓ
(
X
,
Y
. This restriction is necessary since otherwise no graphs other than paths could be
EAP. Namely, if three collinear points are allowed, then for any given
y
-leveling there
would exist an
x
-leveling such that the resulting drawing has edges that overlap each
other. These trivial counterexamples are avoided by restricting the definition to those
x
-levelings that do not cause three collinear points. The interplay between AEP and
2
The names AEP and EAP are acronyms coming from the definitions of the AEP and EAP
graphs, respectively. Namely, a graph is an AEPgraph if “for
A
ny
y
-leveling,there
E
xists an
x
-leveling such that the resulting drawing is
P
lanar”, while a graph is EAP if “there
E
xists a
y
-leveling such that for
A
ny
x
-leveling the resulting drawing is
P
lanar”.
