Information Technology Reference
In-Depth Information
more than two interior faces
C
3
and the connecting faces
F
. An orientation of
the edges of
venation
(
G
) is called
valid
if all edges are oriented and:
•
every vertex in
C
2
has only incoming arcs,
•
every vertex in
C
1
has at most one outgoing arc,
•
every vertex in
C
0
has at most two outgoing arcs,
every vertex in
F
has at precisely one outgoing arc.
We need one more definition, which will make it possible to decide how many
suspensions are needed.
•
Dividing Path.
Let
c
a component of
(
G
) with two interior faces,
f
and
f
. An edge on the boundary of
G
with one end on
f
, is called a
petiole
of
f
.
A simple path
P
, between two boundary vertices of a biconnected outerplanar
graph is said to be a
dividing path
for
c
if
[D1] there is at most one edge of
c
in
P
, and,
[D2] the interior faces of
c
are on opposite sides of
P
, and,
[D3] each face has at least one petiole that is not completely in
P
.
vein
Fig. 2.
A dividing path (red) and petioles (dashed), a valid orientation and a 3TTR
Theorem 1.
Let G be a biconnected outerplanar graph and v
2
the number of
degree two vertices in of G.Letk be an integer such that
2
<k
≤
v
2
if v
2
≥
3
and let k
=3
otherwise. A biconnected outerplanar graph has a kTTR iff
[K1]
Each component of
vein
(
G
)
has at most two interior faces.
[K2]
The graph
(
G
)
admits a valid orientation.
[K3]
There is a way to select k vertices of degree 2 in G, such that, for every
component c
venation
C
2
, there are two representatives in this set, v
i
,v
j
,and
between the representatives there is a dividing path for c.
∈
References
1. Fowler, J.J.: Strongly-Connected Outerplanar Graphs with Proper Touching Trian-
gle Representations. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242,
pp. 155-160. Springer, Heidelberg (2013)
2. Gansner, E.R., Hu, Y., Kobourov, S.G.: On Touching Triangle Graphs. In: Brandes,
U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 250-261. Springer, Heidelberg
(2011)
