On Embedding an Outer-Planar Graph in a Point Set

Bose, Prosenjit (1998) On Embedding an Outer-Planar Graph in a Point Set. In: Graph Drawing 5th International Symposium, GD '97, September 18-20, 1997 , pp. 25-36(Official URL: http://dx.doi.org/10.1007/3-540-63938-1_47).

Full text not available from this repository.

Abstract

Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log³ n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [GMPP91, CU96] that requires O(n²) time. Our algorithm is near-optimal as there is an \Omega (n log n) lower bound for the problem [BMS95]. We present a simpler O(nd) time and an O(n) space algorithm to compute a straight-line embedding of G in P where log n \leq d \leq 2n is the lenght of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(n log n) and O(n²) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal \theta (n log n) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-63938-1_47
Classifications: P Styles > P.720 Straight-line
G Algorithms and Complexity > G.490 Embeddings
M Methods > M.600 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/175

Actions (login required)

View Item View Item