Upward Numbering Testing for Triconnected Graphs

Chandramouli, M. and Diwan, A. A. (1996) Upward Numbering Testing for Triconnected Graphs. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 140-151 (Official URL: http://dx.doi.org/10.1007/BFb0021798).

Full text not available from this repository.

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.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021798
Classifications:P Styles > P.840 Upward
P Styles > P.540 Planar
ID Code:55

Repository Staff Only: item control page

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.