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