Embedding problems for paths with direction constrained edges

We determine the reachability properties of the embeddings in R3 of a directed path, in the graph-theoretic sense, whose edges have each been assigned a desired direction (East, West, North, South, Up, or Down) but no length. We ask which points of R3 can be reached by the terminus of an embedding of such a path, by choosing appropriate positive lengths for the edges, if the embedded path starts at the origin, does not intersect itself, and respects the directions pre-assigned to its edges. This problem arises in the context of extending planar graph embedding techniques and VLSI rectilinear layout techniques from 2D to 3D. We give a combinatorial characterization of reachability that yields linear time recognition and layout algorithms. Finally, we extend our characterization to Rd, d>3.

Authors

• Giuseppe Di Battista
• Giuseppe Liotta
• Anna Lubiw
• Sue Whitesides

Keywords

• Shape
• Embedding
• Path
• Rectilinear layout