Finding a Minimum-depth Embedding of a Planar Graph in O(n 4) Time
Angelini, Patrizio
Di Battista, Giuseppe Patrignani, Maurizio
Di Battista, Giuseppe
Patrignani, Maurizio
Citations
Altmetric:
Abstract
Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O(n 4)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding.
Description
Date
2009
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Planar embedding, Minimum depth, Planar graphs, Triconnected components
Citation
Angelini, Patrizio, Giuseppe Di Battista, and Maurizio Patrignani. “Finding a Minimum-Depth Embedding of a Planar Graph in O(N4) Time.” Algorithmica 60 (4): 890–937. 2011.