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. -

Pizzonia, M., Walter, D. (2003). Upward Embeddings and Orientations of Undirected Planar Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 7(2), 221-241 [10.7155/jgaa.00068].

Upward Embeddings and Orientations of Undirected Planar Graphs

PIZZONIA, MAURIZIO;
2003-01-01

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. -
2003
Pizzonia, M., Walter, D. (2003). Upward Embeddings and Orientations of Undirected Planar Graphs. JOURNAL OF GRAPH ALGORITHMS AND APPLICATIONS, 7(2), 221-241 [10.7155/jgaa.00068].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/135691
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 13
  • ???jsp.display-item.citation.isi??? ND
social impact