On the complexity of embedding planar graphs to minimize certain distance measures
- 1 June 1990
- journal article
- Published by Springer Science and Business Media LLC in Algorithmica
- Vol. 5 (1-4), 93-109
- https://doi.org/10.1007/bf01840379
Abstract
We present polynomial-time algorithms for computing an embedding of a planar graph that minimizes the outerplanarity, or the width, or the radius, or some other measures of distance to the outer face. On the other hand, we show it is NP-hard to compute an embedding that minimizes the diameter of the dual graph.This publication has 6 references indexed in Scilit:
- Optimal enclosing regions in planar graphsNetworks, 1989
- On the Complexity of Covering Vertices by Faces in a Planar GraphSIAM Journal on Computing, 1988
- Multi-layer grid embeddingsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1985
- Graph minors. III. Planar tree-widthJournal of Combinatorial Theory, Series B, 1984
- Approximation algorithms for NP-complete problems on planar graphsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1983
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973