Information Technology Reference
In-Depth Information
v
v
f
f
u
u
w
w
v
(a)
(b)
Fig. 1.
Augmentation technique for removing cutvertices. (a) The graph
G
is drawn solid, the
exclusive edges of
H
are dashed. (b) The modified graphs
G
(solid) and
H
(exclusive edges are
dashed).
this way. Now
H
contains
G
as an induced subgraph. Since
ʓ
is induced 0-universal,
there exists a straight-line drawing of
H
that extends
ʓ
. To obtain a 1-bend drawing
of
H
that extends
ʓ
, we remove from this drawing the edges
v
u
and
v
w
for each angle
of
G
. Now each edge
xv
of
H
,where
v
is a cutvertex of
G
, is drawn with one bend at
the position of the representative vertex of the corresponding angle. We can remove any
overlaps of segments by slightly moving the bend points apart from each other without
creating any crossings. Thus
ʓ
is induced 1-universal.
Corollary 3.
Every connected plane graphhas a
3
-universaldrawing.
We note that Theorem 1 follows easily by applying one of Theorems 2, 3 and Corol-
laries 2, 3 to the common graph of the S
EFE
embedding.
4
SEFE Drawing for General Graphs
Unfortunately, universal drawings cannot be used to prove the existence of S
EFE
draw-
ings with few bends in general. Namely, Pach and Wenger [16] showed that drawing a
planar graph with fixed vertex locations may require an edge with
ʘ
(
n
) bends. Thus,
even a graph consisting only of
n
isolated vertices has no (induced)
o
(
n
)-universal
drawing.
Our goal is to show that any S
EFE
embedding of two graphs
G
1
and
G
2
with
common graph
G
=
G
1
∩
G
2
admits a (0
,c
)-drawing for some constant
c
. Unlike
the previous constructions, this result does not generalize to an arbitrary number of
graphs intersecting in a sunflower-fashion. In fact, we will see later, in Section 5, that
for
k
graphs
ʩ
(
√
2
k
/k
) bends per edge are necessary even in the case of sunflower-
intersection.
As a first step, we show how to construct a (0
,
3)-drawing of (
G
1
,G
2
) if the common
graph is an induced subgraph of
G
1
and
G
2
, respectively, and where we require that
each connected component of the common graph is biconnected. Afterwards, we apply
the technique from Theorem 3 to treat cutvertices in the connected components of
G
,
resulting in (0
,
4)-drawingswhen
G
is an induced subgraph. Then Lemma 2 implies the
existence of a (0
,
9)-drawing for any S
EFE
embedding.
