Journal of Graph Algorithms and Applications
|Home||Issues||Aims and Scope||Instructions for Authors|
Embedding Four-directional Paths on Convex Point Sets
Oswin Aichholzer, Thomas Hackl, Sarah Lutteropp, Tamara Mchedlidze, and Birgit Vogtenhuber
Vol. 19, no. 2, pp. 743-759, 2015. Regular paper.
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 out of the four labels are used. A direction-consistent embedding of an n-vertex three- or 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.
Submitted: October 2014.
Accepted: August 2015.
Final: September 2015.
Published: November 2015.