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

oriented path [9]. Despite several independent approaches to attack the problem by dif-
ferent research groups, this question is still unsolved. However, it was answered in the
affirmative for several special cases of paths and tournaments. We use the following
definitions to list these results. A vertex of a digraph which is either a source or a sink
is called a switch . An oriented path whose edges are all oriented in the same direction
is called monotone . For the following cases it was shown that every upward tournament
contains a planar copy of each oriented path: the vertices of the tournament are in con-
vex position [9], the oriented path has at most 3 switches [9], the oriented path has at
most 5 switches and at least two of its monotone subpaths contain a single edge[5],the
oriented path where every sink is directly followed by a source [9]. It was also shown
that each oriented path of size n is contained in any upward geometric tournament of
size n 2 k− 2 ,where k is the number of switches [5]. This result was later improved to
( n 1) 2 +1 in [15]. Recently, with the help of a computer, we could verify that every

upward geometric tournament of size 10 contains a planar copy of any oriented path as
a spanning subgraph. This was done by exhaustive testing of all distinct directed order
types, that is, all order types [2] with an additional combinatorial upward direction.
The question whether any upward geometric tournament contains a planar copy of
any oriented path was originally stated in terms of so-called pointsetembeddings .Here
we are given a set S of n points in the plane and a planar n -vertex graph G ,andwe
are asked to determine whether G has a planar straight-line drawing where each ver-
tex of G is mapped to a distinct point of S . This problem has been extensively studied
and many exciting facts were established, see for example [6,8,10,11,13]. In the
upward counterpart of point set embeddings, G is an upward planar digraph and the ob-
tained drawing is additionally required to be upwards oriented. Such a drawing,ifitex-
ists, is called an upward pointsetembedding . Upward point set embeddings have been
studied for different classes of digraphs [5,7,9,14]. Observe that the question whether
any upward geometric tournament contains a planar copy of any oriented path is equiv-
alent to asking whether any oriented path has an upward planar embedding on any set
of n points. We will refer to the latter as the oriented path question .
The number of distinct plane embeddingsofan(undirected) spanning path on a
point set could provide us some additional evidence for the oriented path question. It
is not difficult to see that if S is a set of n points in convex position, then it admits
n 2 n− 3 distinct plane spanning path embeddings. Further it is known that this is the
minimumnumber of distinct plane spanning path embeddings that a point set can admit,
i.e., convex point sets minimize this number [3]. Comparing this lower bound with the
number of distinct oriented paths, which is 2 n− 1 ,itsounds even surprising that every
oriented path has an upward planar embedding on every convex point set [9]. In order to
approach the oriented path question in its general form, we aim to understand better how
the nature of the problem changes when in addition to planarity of a path one requires
its upwardness. To this end, we generalize the oriented path problem with respect to
the number of considered directions (see Section 2 for a rigorous definition). Observe
that, instead of considering an oriented path, one can consider a monotone path with
labels on edges that declare whether an edgeisrequired to point up or down. In this
work we study monotone paths with four possible labels on the edges: up, down, left,
and right. We call such paths four-directional ,and three-directional if at most three

−