Abstract
In this paper, we look at the problem of upward planar drawings of planar graphs whose vertices have preassigned y-coordinates. We give a linear time algorithm for testing whether such an embedding is feasible for triconnected labelled graphs.
Chapter PDF
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
G. Di Battista and E. Nardelli. An Algorithm for Planarity Testing of Hierarchical Graphs, volume 246 of Lecture Notes in Computer Science, pages 277–289. Springer-Verlag, 1987.
G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoretical Computer Science, 61:175–198, 1988.
P. Bertolazzi, G. Di Battista, G. Liotta, and C. Mannino. Upward drawings of triconnected digraphs. Algorithmica, to appear.
M. Chandramouli. Upward Planar Graph Drawings. PhD thesis, IIT Bombay, 1994.
M. Chandramouli and A. A. Diwan. Intersection graphs of horizontal and vertical line segments in the plane, 1992. Unpublished manuscript.
A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. In Graph Drawing 94, DIMACS, 1994.
L. S. Heath and S. Pemmaraju. Recognizing leveled-planar dags in linear time. In Proceedings of Graph Drawing '95, 1995.
M. D. Hutton and A. Lubiw. Upward planar drawing of single source acyclic digraphs. In Proc. ACM-SIAM Symposium on Discrete Algorithms, pages 203–211, 1991.
D. R. Kelly. Fundamentals of planar ordered sets. Discrete Mathematics, 63:197–216, 1987.
J. Kratochvil. A special planar satisfiability problem and some consequences of its np-completeness. Discrete Appl. Math. (to appear).
X. Lin. Analysis of Algorithms for Drawing Graphs. PhD thesis, Department of Computer Science, University of Queensland, 1992.
R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Disc. and Comp. Geometry, 1(4):321–341, 1986.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chandramouli, M., Diwan, A.A. (1996). Upward numbering testing for triconnected graphs. In: Brandenburg, F.J. (eds) Graph Drawing. GD 1995. Lecture Notes in Computer Science, vol 1027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021798
Download citation
DOI: https://doi.org/10.1007/BFb0021798
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-60723-6
Online ISBN: 978-3-540-49351-8
eBook Packages: Springer Book Archive