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

Theorem 2. There exists a one-sided pointset S and an

{ U,D,L,R }

-path P such that

there is no PDCE of P on S .

A one-sided point set S is a special case of a convex point set, such that b ( S ) and
t ( S ) are consecutive. However, as Theorem 2 states, such a point set does not always
admit a PDCE of every four-directional path. On the other hand, consider a one-sided
convex point set S where one of the following pairs represents a clockwise consecu-
tive subset of S : ( i ) t ( S ) and ( S ), ( ii ) r ( S ) and t ( S ), ( iii ) b ( S ) and r ( S ), ( iv ) ( S )
and b ( S ).Such a point set is called quarter-convex . It can be easily seen that every
quarter-convex point set admits a PDCE of any four-directional path. Actually, in case
( i ) an edge pointing right always points up and an edge pointing left always points
down. Thus, the problem of embedding a

{ U,D,R,L }

-path is reduced to embedding a

{ U,D }

-path, which always admits a PDCE on any convex point set [9]. Similar reduc-
tions can be made for any other type of a quarter-convex point set. Therefore, we state
the following:

Observation 4. Any { U,D,L,R } -pathhas aPDCE on any quarter-convex pointset.

Based on Lemma 1, it is easy to derive a dynamic programming algorithm to decide
whether a four-directional path admits a PDCE on a convex point set. This is formal-
ized in the following theorem. A similar algorithm, described in [14], tests whether an
upward planar digraph admits an upward planar embedding on a convex point set.

Theorem 3. Let P be an n -vertex four-directionalpathand S be a convex pointset.It
can be decided in O ( n 2 ) time whether P admits aPDCE on S .

6Con lu ion

We i nve s t igated the question of finding a planar direction-consistent embedding on a
convex point set for any given four-directional path. We have shown that this is always
possible for paths that are restricted to at most three outofthefour directions. To the
contrary, we have provided an example showing that for paths using all four directions,
this is not always possible. We also presented an O ( n 2 ) time algorithm to decide em-
beddability for a given four-directional path and convex point set.
The most challenging open problem is to determine whether any two- or three-
directional path always admits a planar direction-consistent embedding on any point
set in general position.

References

1. Aichholzer, O., Hackl, T., Lutteropp, S., Mchedlidze, T., Vogtenhuber, B.: Embedding four-
directional paths on convex point sets. arXiv e-prints arXiv:1408.4933 [cs.CG] (2014)
2. Aichholzer, O., Krasser, H.: The point set order type data base: A collection of applica-
tions and results. In: 13th Annual Canadian Conference on Computational Geometry (CCCG
2001), pp. 17-20 (2001)
3. Aichholzer, O., Hackl, T., Huemer, C., Hurtado, F., Krasser, H., Vogtenhuber, B.: On the
number of plane geometric graphs. Graphs and Comb. 23(1), 67-84 (2007)