Information Technology Reference
In-Depth Information
Lemma 1.
Let
ˁ
=(
v
1
,...,v
k
)
be a path such thatforany
i<j
,
i,j
∈{
1
,...,k
−
}
1
,
(
−−−ₒ
v
i
v
i
+1
,
−−−−ₒ
∠
v
j
v
j
+1
)
≤
90
ⓦ
.Then,
ˁ
hasincreasing chords.
it is
Let
G
=(
V,E
) be a connected graph. A
separating
k
-set
is a set of
k
vertices whose
removal disconnects the graph. A vertex forming a separating 1-set is called
cutvertex
.A
graph is
c
-connected
if it does not admit a separating
k
-set with
k
1; 2-connected
graphs are also called
biconnected
. A connected graph is biconnected if and only if it
does not contain a cutvertex. A
block
is a maximal biconnected subgraph. The
block-
cutvertex tree
(or
BC-tree
)
T
G
of
G
has a
B
-node
for each block of
G
,a
C
-node
for
each cutvertex of
G
and, for each block
ʽ
containing acutvertex
v
,anedge between the
corresponding
B
-and
C
-node. We associate
B
-nodes with their corresponding blocks
and
C
-nodes with their corresponding cutvertices.
The following notation follows the work of Angelini et al. [5]. Let
T
G
be rooted
at some block
ʽ
containing a non-cutvertex (such a block
ʽ
always exists). For each
block
μ
≤
c
−
=
ʽ
,let
ˀ
(
μ
) denote the
parentblock
of
μ
, i.e., the grandparent of
μ
in
T
G
.
Let
ˀ
2
(
μ
) denote the parent block of
ˀ
(
μ
) and, generally,
ˀ
i
+1
(
μ
) the parent block
of
ˀ
i
(
μ
).Further, we define the
root
r
(
μ
) of
μ
as the cutvertex contained in both
μ
and
ˀ
(
μ
). Note that
r
(
μ
) is the parent of
μ
in
T
G
. In addition, for the root node
ʽ
of
T
G
,wedefine
r
(
ʽ
) to be some non-cutvertex of
ʽ
. Let depth
B
(
μ
) denote the number
of
B
-nodes on the
ʽμ
-path in
T
G
minus 1, and let depth
C
(
r
(
μ
)) = depth
B
(
μ
).If
μ
is
a leaf of
T
G
,wecallita
leafblock
.
If every block of
G
is outerplanar,
G
is called a
cactus
.Ina
binary
cactusevery
cutvertex is part of exactly two blocks. For a binary cactus
G
with a block
μ
containing
acutvertex
v
,let
G
μ
denote the maximal connected subgraph containing
v
butnoother
vertex of
μ
. We say that
G
μ
is a
subcactus
of
G
.
A cactusis
triangulated
if each of its blocks is internally triangulated. A
triangular
fan withvertices
V
t
=
{
v
0
,v
1
,...,v
k
}
and root
v
0
is a graph on
V
t
with edges
v
i
v
i
+1
,
i
=1
,...,k
1,aswellas
v
0
v
i
,
i
=1
,...,k
.Letus consider a special kind of
triangulated cactuses, each of whose blocks
μ
is either an edgeora
triangularfan
with
root
r
(
μ
). We call such a cactus
downward-triangulated
and every edge of a block
μ
incident to
r
(
μ
) a
downward
edge.
For a fixed straight-line drawing of a binary cactus
G
,wedefinesets
U
(
G
)=
{
# »
−
{
#
uv
|
# »
r
(
μ
)
v
|
μ
is a block of
G
containing
v, v
=
r
(
μ
)
}
and
D
(
G
)=
vu
∈
U
(
G
)
}
,
i.e. the sets of
upward
and
downward
directions of
G
.
3
Graphs with Self-Approaching Drawings
Anatural approach to construct (not necessarily plane) self-approaching drawingsisto
construct a self-approaching drawing of a spanning subgraph. For instance, to draw a
graph
G
containing a Hamiltonian path
H
with increasing chords, we simply draw
H
consecutively on a line. In this section, we consider 3-connected planar graphs and the
special case of triangulations, which addresses an open question of Alamdari et al. [1].
These graphs are known to have a spanning binary cactus[5,13].Angelini et al. [5]
showed that every triangulation has a spanning downward-triangulated binary cactus.
