Information Technology Reference
In-Depth Information
Consider a straight-line drawing
ʓ
of a planar graph
G
. A face
f
is
star-shaped
if it
contains a point
p
such that the straight-line segment from
p
to each vertex of
f
lies in-
side
f
.Thesetofallsuch points
p
is the
kernel
of the face. We say that
ʓ
is
star-shaped
if all its faces are
star-shaped
. We will frequently use the following lemma, stating that
any planar graph admits a star-shaped drawing.Ofcourse it is always possible to find a
drawing where the vertices are in general position. This implies that the kernel of each
face has positive area.
Lemma 1.
Let
G
=(
V,E
)
be a plane graph.There exists a star-shaped planarstraight-
linedrawing of
G
such thatthe kernel of theouter face contains points on or outside of
theconvex hull of the vertices in
G
.
Proof.
To construct such a drawing, we create for each face
f
of
G
anewvertex
v
f
that
is connected to vertices incident to
f
and embed it inside
f
. Afterwards, we triangulate
the graph in such a way that the vertex
v
0
added for the outer face
o
is incident to the
outer face. Call the resultinggraph
G
.
We then produce a straight-line drawing of
G
. Since this drawing is planar and each
vertex
v
f
is connected by straight-line segments to all vertices incident to
f
,remov-
ing
v
f
yields a drawing where face
f
is star-shaped. We remove all vertices
v
f
of all
faces to obtain a star-shaped drawing. Note that the outer face
o
of
G
is a triangle, and
hence
v
o
lies on or outside of the convex hull of
G
.
For an instance
G
1
=(
V
1
,E
1
) and
G
2
=(
V
2
,E
2
) of S
EFE
, we say that the com-
mon graph
G
=(
V,E
) is
induced
if the induced subgraph of
V
in
G
1
and
G
2
is
G
.
This is equivalent to the statement that each exclusive edge has at least one endpoint
that is not in
V
.Assuming that
G
is induced will often simplify ourarguments. Given a
non-induced instance (
G
1
,G
2
) of S
EFE
together with a S
EFE
embedding, we can con-
struct its
associated induced instance
by subdividing each exclusive edge once (with
an exclusive vertex). Note that this operation does not change the common graph
G
.
By interpreting the subdivision vertices as bends in a drawing of the associated induced
instance, we obtain the following lemma.
Lemma 2.
Let
(
G
1
,G
2
)
be an instance of
S
EFE
withafixed
S
EFE
embedding andlet
(
G
1
,G
2
)
be the associated induced instance. If
(
G
1
,G
2
)
admits a
(0
,c
)
-drawing,then
(
G
1
,G
2
)
admits a
(0
,
2
c
+1)
-drawing.
Proof.
Consider a (0
,c
)-drawing of (
G
1
,G
2
). We can interpret it as a S
EFE
drawing
of (
G
1
,G
2
) by interpreting the subdivision vertices as bends. Consider a subdivided
edge
e
.Byassumption, each half-edge into which
e
is subdivided has at most
c
bends.
Together with the additional bend at the subdivision vertex this amounts to a total of
2
c
+1bends per edge.
3
SEFE Drawing with (Bi-)Connected Common Graph
In this section we study realizations of S
EFE
embeddings where the common graph is
biconnected or connected. The main result of this section is the following theorem.
