Sue Whitesides

Embedding Problems for Paths and Cycles with Direction-Constrained Edges

Abstract for the Combinatorics and Number Theory Seminar
2001 November 14

An orthogonal shape path is a sequence of n axis-aligned direction vectors in Rd. To realize a shape path means to assign a positive integer length to each element in the sequence so that the resulting orthogonal polygonal curve is non-self-intersecting. Shape cycles may be defined in an analogous way.

We study reachability properties of shape paths. For example, we characterize those shape paths that have realizations that start at the origin and, with an appropriate assignment of lengths to their elements, end at a point with all positive coordinates.

We also characterize those cyclic sequences of axis-aligned direction vectors that can be realized as closed, orthogonal, polygonal curves in R3.