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. -
Angelini, P., DI BATTISTA, G., Patrignani, M. (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-01-01
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. -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.
