Embedding Four-Directional Paths on Convex Point Sets - Graph Drawing - page 356

outofthefour labels are used. An embedding of such a path on a point set where
each edge points into the direction specified by its label is called direction-consistent .
We s tudy planar direction-consistent embeddings of three- and four-directional paths
on convex point sets. Recall that convex point sets are extremal in the sense that they
minimize the number of plane embeddingsof(undirected) spanning paths. We provide
a complete picture regarding four-directional paths and convex point sets. Ourresults
are as follows:

- Every three-directional path admits a planar direction-consistent embedding on any
convex point set.
- There exists a four-directional path P and a one-sided 1 convex point set S such that
P does not admit a planar direction-consistent embedding on S . On the other hand,
afour-directional path always admits a planar direction-consistent embedding for
special cases of one-sided point sets, namely so-called quarter-convex point sets.
- Given a four-directional path P and a convex point set S , we can decide in O ( n 2 )
time whether P admits a planar direction-consistent embedding on S .

Ourstudy is also motivated by applications similar to those of upward point set em-
beddings, i.e., any situation where a hierarchical structure must be represented and ad-
ditional constraints on the positions of vertices are given. Our scenario, where instead
of two directions the edges can point into four directions, allows for a more detailed
control over a drawing.
The remainder of the paper is organized as follows. In Section 2, we give the neces-
sary definitions. In Section 3, we prove several preliminary results which are utilized in
our main Section 4, where the existence of a planar direction-consistent embedding of
a three-directional path on a convex point set is shown. All results on four-directional
paths are concentrated in Section 5. Due to space constraints omitted proofs can be
found in the full version [1].

2 Definitions

Graphs. The graphs we study in this paper are directed and we denote by ( u,v ) an
edge directed from u to v . A directed edge when drawn as a straight-line segment is
said to point up or being upward , if its source is below its sink. Similarly we define the
notions of pointing down , left ,and right .Ourstudy concentrates on directed paths each
edge of which is assigned one of four labels U,D,L,R , which means that (when the
path is embedded on a point set) this edgeisrequired to point up, down, left, or right,
respectively. For simplicity, we will denote such a path containing vertices v 1 ,...,v n
by P = d 1 ,...,d n− 1 ,where d i ∈{ U,D,L,R } , 1 ≤ i ≤ n − 1.Let T ↆ{ U,D,L,R } .

If d i ∈ -directionalpath in order

to emphasize the number of directions it contains. We denote by P i,j = d i ,...,d j ,
1

T , 1 ≤ i ≤ n − 1,then P is called T -path and | T |

≤ i ≤ j ≤ n − 1,asubpath of P . In addition, we define P i,i− 1 = v i .

1

A convex point set is called one-sided if all of its points lie on the same side of the line through
its bottommost and topmost points.