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 , 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
URI: http://gdea.informatik.uni-koeln.de/id/eprint/98

Actions (login required)

View Item View Item