"On Embedding an Outer-Planar Graph in a Point Set"
SPEAKER:
Prof. Prosenjit Bose, School of Computer Science, Carleton University
Given an n-vertex outer-planar graph G and a set P of n points
in the plane, we present an O(n log3 n) time and O(n) space
algorithm to compute a straight-line embedding of G in P,
improving upon the a previous algorithm that
requires O(n2) time. Our algorithm is near-optimal as there is an
Omega(n log n) lower bound for the problem.
We present a simpler O(n d) 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(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 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.
This information is available at
http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and
suggestions for speakers to Therese Biedl at
therese@cgm.cs.mcgill.ca.