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 flow model. We take advantage of such a flow 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.
Upward Embeddings and Orientations of Undirected Planar Graphs
DIDIMO, WALTER;
2001
Abstract
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 flow model. We take advantage of such a flow 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
