Information Technology Reference
In-Depth Information
2. We show how to construct plane increasing-chord drawingsfor planar 3-trees (a
special class of triangulations) using Schnyder realizers (Sect. 4). To the best of our
knowledge, this is the first construction for this graph class, even for greedy and strongly
monotone plane drawings, which addresses an open question of Angelini et al. [2].
3. We show that, similarly to the greedy case, the hyperbolic plane
H
2
allows repre-
2 (Sect. 5). We prove that a tree has a self-
approaching or increasing-chord drawing in
senting a broader class of graphs than
R
2 if and only if it either has maximum
degree 3 or is a subdivision of K 1 , 4 (this is not the case in
H
2 ; see the characterization
by Alamdari et al. [1]), implying every 3-connected planar graph has an increasing-
chord drawing. We also show how to construct planar increasing-chord drawingsof
binary cactuses in
R
2 .
H
2
Preliminaries
2 ,letray( a, b ) denote the ray with origin a and direction # ab
and ray( a, # bc ) the ray with origin a and direction # bc .Letdir( ab ) be the vector # ab nor-
malized to unit length. Let
For points a,b,c,d
R
( # ab, # cd ) denote the smaller angle formed by the two vectors
[0 , 2 ˀ ],let R ʱ denote the rotation matrix cos ʱ − sin ʱ
sin ʱ cos ʱ .
# ab and # cd . For an angle ʱ
# v 1 , # v 2 with dir( # v 2 )= R ʱ ·
dir( # v 1 ), ʱ
ccw ( # v 1 , # v 2 ):=
For vectors
[0 , 2 ˀ ), we write
ʱ .Further, let [ # v 1 , # v 2 ] denote the cone of directions
{ # v
dir( # v )= R ʲ ·
dir( # v 1 ), ʲ
|
[ # v 1 , # v 2 ]
[0 ]
:= ʱ be its size . For a set of directions D ,let D denote a minimum
cone of directions containing D ,andlet
}
.Let
|
|
|
D
|
|
D
|
|
D
|
< 180 , D is
=
. Note that if
unique.
We r euse some notation from the work of Alamdari et al. [1]. For points p,q ∈
2 ,p = q ,let l pq denote the halfplane not containing p bounded by the line through q
orthogonal to the segment pq . A piecewise-smooth curve is self-approaching if and
only if for each point a on the curve, the line perpendicular to the curve at a does not
intersect the curve at a later point [11]. This leads to the following characterization of
self-approaching paths.
R
Fact 1 (Corollary 2 in [1]). Let ˁ =( v 1 ,v 2 ,...,v k ) be a directed path embedded
in
2 with straight-linesegments. Then, ˁ is self-approaching if andonly if for all
R
k ,the point v j lies in l v i v i +1 .
1
i<j
We shall denote the reverse of a path ˁ by ˁ 1 .Let ˁ =
( v 1 ,v 2 ,...,v k ) be a self-approaching path. Define front( ˁ )=
k− 1
i =1 l v i v i +1 , see also Fig.1.Using Fact 1, we can decide
whether a concatenation of two paths is self-approaching.
ˁ
Fact 2. Let ˁ 1 =( v 1 ,..., v k ) and ˁ 2 =( v k ,v k +1 , ..., v m ) be
self-approaching paths. Thepath ˁ 1 2 := ( v 1 ,...,v k ,v k +1 ,
...,v m ) is self-approaching if andonly if ˁ 2
Fig. 1. self-approach-
ing path ˁ and front( ˁ )
front( ˁ 1 ) .
Apath ˁ has increasing chords if for any points a,b,c,d in this order along ˁ ,itis
dist( b,c )
dist( a, d ). A path has increasing chords if and only if it is self-approaching
in both directions. The following result is easy to see.
 
Search WWH ::




Custom Search