Information Technology Reference
In-Depth Information
Touching Triangle Represenations in a
k
-gon
of Biconnected Outerplanar Graphs
Nieke Aerts
Technische Universitat Berlin, Institut fur Mathematik, Berlin, Germany
aerts@math.tu-berlin.de
Introduction.
A side-contact representation by triangles, without holes, is
called a touching triangle representation. Gansner et al. have shown that ev-
ery biconnected outerplanar graph has a touching triangle representation [2].
In their construction the boundary is a polygon with concave and convex an-
gles. Fowler characterized the strongly-connected outerplanar graphs that have
a proper touching triangle representation [1], i.e., the outer face is a triangle
as well. An outerplanar graph is strongly-connected if it is biconnected and the
graph induced by the interior edges is connected. Here we expand this character-
ization to biconnected outerplanar graphs. Moreover, the characterization allows
for deciding precisely how many corners the boundary polygon needs to have. A
touching triangle representation in a
k
-gon is called a
k
TTR.
Definitions.
First we construct the graph
H
such that
G
is the weak dual of
H
. Start with the weak dual of
G
. Add an edge and a new endpoint for every
boundary edge of
G
. The newly added points are cyclically connected. Every
boundary edge, whose contraction does not induce a 2-face, is contracted.
Let
(
G
) be the graph consisting of all strictly interior edges of
G
and
their endpoints. The venation graph of
vein
vein
(
G
), denoted by
venation
(
G
), is
the graph that has as vertices the components of
(
G
) and the faces between
two components. There is an edge between a component and a face if and only
if the face has a chord of this component on its boundary. There are no other
edges.
The vertices of the venation graph can be divided into five classes, the compo-
nents without interior face
C
0
, the components with precisely one interior face
C
1
, the components with precisely two interior faces
C
2
, the components with
vein
G
H
vein
(
G
)
Fig. 1.
A biconnected outerplanar graph
G
, its auxiliary graph
H
and
vein
(
G
)
