Upward Planar Drawing of Single Source Acyclic Digraphs

A upward plane drawing of a directed acyclic graph is a straight line drawing in the Euclidean plane such that all directed arcs point upwards. Thomassen [30] has given a non-algorithmic, graph-theoretic characterization of those directed graphs with a single source that admit an upward drawing. We present an efficient algorithm to test whether a given single-source acyclic digraph has a plane upward drawing and, if so, to find a representation of one such drawing. The algorithm decomposes the graph into biconnected and triconnected components, and defines conditions for merging the components into an upward drawing of the original graph. For the triconnected components we provide a linear algorithm to test whether a given plane representation admits an upward drawing with the same faces and outer face, which also gives a simpler (and algorithmic) proof of Thomassen's result. The entire testing algorithm (for general single source directed acyclic graphs) operates in O(n²) time and..