1. Embedding problems for paths with direction constrained edges
- Author
-
Battista, Giuseppe Di, Liotta, Giuseppe, Lubiw, Anna, and Whitesides, Sue
- Subjects
- *
EMBEDDINGS (Mathematics) , *GRAPHIC methods - Abstract
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 ofR3 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 toRd, d>3 . [Copyright &y& Elsevier]- Published
- 2002
- Full Text
- View/download PDF