Upward Planarity Testing of Outerplanar Dags (Extended Abstract)

Papakostas, Achilleas (1995) Upward Planarity Testing of Outerplanar Dags (Extended Abstract). In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994, Princeton, New Jersey, USA , pp. 298-306 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_385).

Full text not available from this repository.


In this paper, we present two polynomial-time algorithms to determine if an outerplanar directed acyclic graph (odag) can be drawn upward planar, that is, drawn in planar straight-line fashion so that all arcs point up. The first algorithm checks if the odag has an upward planar drawing that is topologically equivalent to the outerplanar embedding of the odag. This algorithm runs in linear time (which is optimal), and is faster than any previous algorithm known. The second algorithm also checks whether an odag has an upward planar drawing but does not insist that the drawing be topologically aquivalent to the outerplanar embedding. This is the first polynomial-time algorithm we known of to solve this problem.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_385
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.770 Planarity Testing
ID Code:98

Repository Staff Only: item control page


P.Bertolazzi and G. Di Battista, On upward drawing testing of triconnected digraphs, Proc. 7th ACM Symp. on Computational Geometry, pp. 272-280, 1991.

P.Bertolazzi, G. Di Battista, C. Mannino and R. Tamassia, Optimal upward planarity testing of single-source digraphs, In: 1st Annual European Symp. on Algorithms, Lecture Notes in Comp. Sci., Springer-Verlag, 1993.

G. Di Battista, W.P. Liu, I. Rival, Bipartite graphs, Upward drawings and Planarity, Information Processing Letters, vol. 36, pp. 317-322, 1990.

G. Di Battista and R. Tamassia, Algorithms for plane representations of acyclic digraphs, Theoretical Computer Science, vol. 61, pp. 175-198, 1988.

H. de Fraysseix, J. Pach, R. Pollack, How to draw a planar graph on a grid, Combinatorica, vol. 10, pp. 41-51, 1990.

A. Garg and R. Tamassia, On the Computational Complexity of Upward and Rectilinear Planarity Testing, to appear in Proc. of Graph Drawing 1994.

J. Hopcroft and R. Tarjan, Efficiente planarity testing, J. Assoc. Comput. Mach., vol. 21, pp. 549-568, 1974.

M.D. Hutton and A. Lubiw, Upward planar drawing of single source acyclic digraphs, Proc. 2nd ACM-SIAM Symp. on Discrete Algorithms, pp. 203-211, 1990.

D. Kelly, On the dimension of partially ordered sets, Discrete Math., vol. 63, pp. 197-216, 1987.

C. Platt, Planar lattices and planar graphs, J. Combin. Theory Ser. B, vol. 21, pp. 30-39, 1976.

W. Schnyder, Embedding planar graphs on the grid, Proc. 1st ACM-SIAM Symp. on Discrete Algorithms, pp. 138-147, 1990.