Information Technology Reference
In-Depth Information
Embedding Four-Directional Paths
on Convex Point Sets
Oswin Aichholzer
1
, Thomas Hackl
1
, Sarah Lutteropp
2
,
Tamara Mchedlidze
2
,andBirgit Vogtenhuber
1
1
Institute for Software Technology, Graz University of Technology, Austria
{
oaich,thackl,bvogt
}
@ist.tugraz.at
2
Institute of Theoretical Informatics, Karlsruhe Institute of Technology, Germany
sarah.lutteropp@student.kit.edu, mched@iti.uka.de
Abstract.
A directed path whose edges are assigned labels “up”, “down”, “right”,
or “left” is called
four-directional
,and
three-directional
if at most three outof
the four labels are used. A
direction-consistentembedding
of an
n
-vertex four-
directional path
P
on a set
S
of
n
points in the plane is a straight-line drawing
of
P
where each vertex of
P
is mapped to a distinct point of
S
and every edge
points to the direction specified by its label. We study planar direction-consistent
embeddings of three- and four-directional paths and provide a complete picture
of the problem for convex point sets.
1
Introduction
In 1974, Rosenfeld proved that every tournament has a spanning
antidirected
path [17]
and conjectured that there exists an integer
n
0
such that every tournament with more
than
n
0
vertices contains every
oriented path
as a spanning subgraph. A tournament is
adigraph whose underlyingundirected structure is a complete graph and an oriented
path is a digraph whose underlyingundirected structure is a simple path. An oriented
path is antidirected if the directions of its edges alternate. During the following decade
several simplifications of Rosenfeld's conjecturehadbeenshowntobetrue. Alspach
and Rosenfeld [4] and Straight [18] settled the conjecture for oriented paths with either
asingle source or a single sink. Forcade [12] proved the conjecture to be trueforevery
tournament whose size is a power of two. Reid and Wormald[16] showed that any tour-
nament of size
n
contains every oriented path of size 2
n/
3 and Zhang [20] improved
this result to
n
1. Finally, in 1986, the conjecture was established by Thomason [19].
More than two decades later, with the expansion of Geometric Graph Theory and
Graph Drawing,ageometric counterpart of Rosenfeld's conjecture was considered. The
subject of this study is an
upward geometric
tournament, that is, a tournament drawn
on the plane with straight-line edges so that each edge points in the upward direction.
It was asked whether an upward geometric tournament contains a planar copy of any
−
O.A. supported by the ESF EUROCORES programme EuroGIGA - ComPoSe, Austrian Sci-
ence Fund (FWF): I 648-N18. T.H. supported by the Austrian Science Fund (FWF): P23629-
N18 'Combinatorial Problems on Geometric Graphs'.
