Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(n log~3 n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n~2) time. Our algorithm is near-optimal as there is an Ω (n log n) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where log n ≤ d ≤ 2n is the length 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~2) 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 Θ(n log n) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.
展开▼
