Upward Embeddings and Orientations of Undirected Planar Graphs - Didimo, Walter; Pizzonia, Maurizio (Journal of Graph Algorithms and Applications, 2003)
An upward embedding of an embedded planar graph specifies, foreach vertex v,which edges are incident on v "above" or "below" and, in turn,induces an upward orientation of the edges from bottom to top.In this paper we characterize the set of all upward embeddings andorientations of an embedded planar graph by using a simple flowmodel, which is related to that described byBousset [] to characterize bipolar orientations. Wetake advantage of such a flow model to compute upward orientationswith the minimum number of sources and sinks of 1-connectedembedded planar graphs.We finally devise a new algorithm for computingvisibility representations of 1-connected planar graphs using ourtheoretic results. <!---->