Abstract
We determine the reachability properties of the embeddings in R 3 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 R 3 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 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 combinatorial characterizations of reachability that yield linear time recognition and layout algorithms.
Research partially supported by operating grants from the Natural Sciences and Engineering Research Council (NSERC) of Canada, by the project “Algorithms for Large Data Sets: Science and Engineering” of the Italian Ministry of University and Scientific and Technological Research (MURST 40%), and by the project “Geometria Computazionale Robusta con Applicazioni alla Grafica ed a CAD” of the Italian National Research Council (CNR).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
T. Biedl, T. Shermer, S. Wismath, and S. Whitesides. Orthogonal 3-D graph drawing. J. Graph Algorithms and Applications, 3(4):63–79, 1999.
R. F. Cohen, P. Eades, T. Lin and F. Ruskey. Three-dimensional graph drawing. Algorithmica, 17(2):199–208, 1997.
G. Di Battista, P. Eades, R. Tamassia, and I. Tollis. Graph Drawing. Prentice Hall, 1999.
G. Di Battista and L. Vismara. Angles of planar triangular graphs. SIAM J. Discrete Math., 9(3):349–359, 1996.
P. Eades, C. Stirk, and S. Whitesides. The techniques of Kolmogorov and Bardzin for three dimensional orthogonal graph drawings. Inform. Process. Lett., 60:97–103, 1996.
P. Eades, A. Symvonis, and S. Whitesides. Two algorithms for three dimensional orthogonal graph drawing. In S. North, Ed, Graph Drawing (Proc. GD’ 96), volume 1190 of Lecture Notes Comput. Sci., pages 139–154. Springer-Verlag, 1997.
A. Garg. New results on drawing angle graphs. Comput. Geom. Theory Appl., 9(1–2):43–82, 1998. Special Issue on Geometric Representations of Graphs, G. Di Battista and R. Tamassia, Eds.
A. Papakostas and I. Tollis. Incremental orthogonal graph drawing in three dimensions. In G. Di Battista, Ed, Graph Drawing (Proc. GD’ 97), volume 1353 of Lecture Notes Comput. Sci., pages 139–154. Springer-Verlag, 1997.
R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421–444, 1987.
G. Vijayan and A. Wigderson. Rectilinear graphs and their embeddings. SIAM J. Comput., 14:355–372, 1985.
V. Vijayan. Geometry of planar graphs with angles. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pages 116–124, 1986.
D. R. Wood. Two-bend three-dimensional orthogonal grid drawing of maximum degree five graphs. Technical Report 98/03, School of Computer Science and Software Engineering, Monash University, 1998.
D. R. Wood. An algorithm for three-dimensional orthogonal graph drawing. In Graph Drawing (Proc. GD’ 98), volume 1547 of Lecture Notes Comput. Sci., pages 332–346. Springer-Verlag, 1998.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Battista, G., Liotta, G., Lubiw, A., Whitesides, S. (2000). Embedding Problems for Paths with Direction Constrained Edges. In: Du, DZ., Eades, P., Estivill-Castro, V., Lin, X., Sharma, A. (eds) Computing and Combinatorics. COCOON 2000. Lecture Notes in Computer Science, vol 1858. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44968-X_7
Download citation
DOI: https://doi.org/10.1007/3-540-44968-X_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67787-1
Online ISBN: 978-3-540-44968-3
eBook Packages: Springer Book Archive