ISSN:
1432-0541
Keywords:
Planar graphs
;
Embedding
;
Outer faces
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01840379
Permalink