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

doi.org/10.1007/3-540-63938-1_47
School of Computer Science

Bose, P. (1997). On embedding an outer-planar graph in a point set. doi:10.1007/3-540-63938-1_47