Information Technology Reference
In-Depth Information
new vertices to triangulate its faces. Note that it may not be possible to triangulate
H
without adding new vertices as this might violate the property of
G
being an induced
subgraph. All vertices and edges that are added during the triangulation can be removed
after a drawing has been found.
The vertices and edges of
H
−
G
are embedded in the faces of
G
. We show that, for
each face
f
of
G
, the parts of
H
G
embedded in
f
can be drawn inside
f
without
any bends. To this end, let
f
be a face of
G
and let
H
denote the subgraph of
H
consisting of the boundary of
f
and all edges and vertices of
H
that are embedded
in
f
.Letfurther
C
denote the facial cycle bounding
f
. Note that
C
is a simple cycle
since
G
is biconnected. Then the graph
H
is a planar graph where one face is bounded
by
C
and all remaining faces are triangles. Hence, considering
C
as the boundary of
the outer face of
H
, it follows that
H
is internally triconnected and, moreover, it is
triconnected if and only if it does not contain a chord of
C
. This is, however, not the
case since
C
is an induced subgraph of
H
. It hence follows that
H
is triconnected.
Thus,
H
is triconnected and its outer vertices have been fixed to a star-shaped polygon
with positive kernel. A result of Hong and Nagamochi [11, Theorem 10] shows that the
given drawing of
C
can be extended to one of
H
without crossings and bends. Since
this reasoning can be applied independently to all faces, we find the claimed extension.
For the outer face we use a technique similar to [10] and position the vertices of
−
H
G
incident to
G
on the boundary of a small disk in the interior of the kernel of
the outer face such that the edges between
G
and
H
−
G
can be drawn in a planar
way without intersecting the interior of the disk. Then, since the positioned exclusive
vertices are in convex position, the remaining drawing can be completed withoutany
bends by a Tutte drawing [19].
−
By applying Lemma 3, we immediately obtain the following corollary.
Corollary 2.
Every biconnected plane graphhas a
1
-universaldrawing.
Theorem 3.
Every connected plane graphhas an induced
1
-universaldrawing.
Proof.
Let
G
be a connected planar graph with a fixed embedding.Weshowhowto
construct an induced 1-universal drawing of
G
.Let
v
be a cutvertex of
G
,let
f
be a
face of
G
on whose boundary
v
occurs at least twice, and let
vu
and
vw
be two edges
incident to
f
and
v
that are consecutive in the circular ordering around
v
. We call such
a configuration an
angle
of
G
. We process this angle by adding to
G
anewvertex
v
with neighbors
u,v
and
w
. We call
v
the
representative vertex
of the angle; see Fig.1.
Call
G
the graph resulting from
G
after processing all angles in this way. Note that
G
is biconnected and hence has an induced 0-universal drawing
ʓ
by Theorem 2.
We claim that the restriction
ʓ
of
ʓ
to
G
is induced 1-universal. Let
H
G
be
aplanegraph that contains
G
as an induced subgraph. For each cutvertex
v
of
G
,the
incident edges of
H
are embedded in one of the angles of
v
.Let
u
and
w
be the other
two vertices of such an angle at
v
and let
vv
1
,...,vv
k
denote the edges of
H
that are
embedded inside this angle. We modify
H
by creating anewvertex
v
that is adjacent
to
u,v
and
w
.Wefurther replace the edges
vv
1
,...,vv
k
by
v
v
1
,...,v
v
k
,whichis
clearly possible in a planar way; see Fig.1,wheretheedges of
E
(
H
)
ↇ
E
(
G
) are
shown dashed. Let
H
be the graph resulting from
H
by treating all angles of
G
in
\
