UPWARD DRAWINGS OF TRICONNECTED DIGRAPHS

A polynomial-time algorithm for testing if a triconnected directed gra ph has an upward drawing is presented. An upward drawing is a planar d rawing such that all the edges flow in a common direction (e.g., from bottom to top). The problem arises in the fields of automatic graph dr awing and ordered sets, and has been open for several years. The propo sed algorithm is based on a new combinatorial characterization that ma ps the problem into a max-flow problem on a sparse network; the time c omplexity is O(n + r(2)), where n is the number of vertices and r is t he number of sources and sinks of the directed graph. If the directed graph has an upward drawing, the algorithm allows us to construct one easily.