Upward Embeddings and Orientations of Undirected Planar Graphs
Walter Didimo, Maurizio Pizzonia · Journal of Graph Algorithms and Applications · 2003
An upward embedding of an embedded planar graph states, for each vertex v, which edges are incident to v \\above" or \\below" and, in turn, induces an upward orientation of the edges. In this paper we characterize the set of all upward embeddings and orientations of a plane graph by using a simple ow model. We take advantage of such a ow model to compute upward orientations with the minimum number of sources and sinks of 1-connected graphs. Our theoretical results allow us to easily compute visibility representations of 1-connected graphs while having a certain control over the width and the height of the computed drawings, and to deal with partial assignments of the upward embeddings \\underlying" the visibility representations. 2 1