Consider an n-vertex planar graph G. We present an O(n^4)-time algorithm for computing an embedding of G with minimum distance from the external face. This bound improves on the best previous bound by an O(n log(n)) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum depth embedding. -

PATRIZIO ANGELINI, GIUSEPPE DI BATTISTA, & MAURIZIO PATRIGNANI (2007). Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time. In 10th Workshop on Algorithms and Data Structures (WADS '07) (pp.287-299). Berlin : SPRINGER-VERLAG [10.1007/978-3-540-73951-7_26].

Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time

ANGELINI, PATRIZIO;DI BATTISTA, Giuseppe;PATRIGNANI, Maurizio
2007

Abstract

Consider an n-vertex planar graph G. We present an O(n^4)-time algorithm for computing an embedding of G with minimum distance from the external face. This bound improves on the best previous bound by an O(n log(n)) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum depth embedding. -
978-3-540-73948-7
PATRIZIO ANGELINI, GIUSEPPE DI BATTISTA, & MAURIZIO PATRIGNANI (2007). Computing a Minimum-Depth Planar Graph Embedding in O(n^4) Time. In 10th Workshop on Algorithms and Data Structures (WADS '07) (pp.287-299). Berlin : SPRINGER-VERLAG [10.1007/978-3-540-73951-7_26].
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: http://hdl.handle.net/11590/173514
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? ND
social impact