Upward Planar Drawing of Single Source Acyclic Digraphs (Extended Abstract)

An upward plane drawing of a directed acyclic graph is a plane drawing of the graph in which each directed edge is represented as a curve monotone increasing in the vertical direction. Thomassen [14] has given a non-algorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward plane drawing. We present an efficient algorithm to test whether a given single-source acyclic digraph has an upward plane drawing and, if so, to find a representation of one such drawing. The algorithm decomposes the graph into biconnected and triconnected components, and de nes conditions for merging the components into an upward plane drawing of the original graph. To handle the triconnected components we provide a linear algorithm to test whether a given plane drawing admits an upward plane drawing with the same faces and outer face, which also gives a simpler, algorithmic proof of Thomassen's result. The entire testing algorithm (for general single-source directed acyclic graphs) operates in O(n²) time and O(n) space