Home | Issues | About JGAA | Instructions for Authors |
Special Issue on Selected Papers from the Seventh International Workshop on Algorithms and Data Structures, WADS 2001
DOI: 10.7155/jgaa.00068
Upward Embeddings and Orientations of Undirected Planar Graphs
Vol. 7, no. 2, pp. 221-241, 2003. Regular paper.
Abstract An upward embedding of an embedded planar graph specifies, for
each 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 and
orientations of an embedded planar graph by using a simple flow
model, which is related to that described by
Bousset [] to characterize bipolar orientations. We
take advantage of such a flow model to compute upward orientations
with the minimum number of sources and sinks of 1-connected
embedded planar graphs.
We finally devise a new algorithm for computing
visibility representations of 1-connected planar graphs using our
theoretic results.
|
Journal Supporters
|