20021201
On embedding an outerplanar graph in a point set
Publication
Publication
Computational Geometry , Volume 23  Issue 3 p. 303 312
Given an /ivertex outerplanar graph G and a set P of n points in the plane, we present an O(;i log3 n) time and O(n) space algorithm to compute a straightline embedding of G in P, improving upon the algorithm in [8,12] that requires O(n2) time. Our algorithm is nearoptimal as there is an E(n logn) lower bound for the problem [4]. We present a simpler O(nd) time and O(/t) space algorithm to compute a straightline embedding of G in F where logn  d  In 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 logn) and O(n2) 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 Q(n logn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices.
Additional Metadata  

Graph drawing, Graph embedding, Straightline embedding  
Computational Geometry  
Organisation  School of Computer Science 
Bose, P. (2002). On embedding an outerplanar graph in a point set. Computational Geometry, 23(3), 303–312.
