8.5. RELATED PROBLEMS 277
straight-line edges [Bos02]. In [Bos02], an O(n log
3
n)-time algorithm is also presented to
compute a straight-line point-set embedding of an out er p lanar graph G on a given set of
points. For trees, an optimal Θ(n log n)-time algorithm is given by Bose et al. [BMS97],
who improve previous results by Ikebe et al. [IPTT94] and Pach and T¨or˝ocsik [PT93].
The problem of decidi ng whether there ex is ts a point set embedding with straight-line
edges of a planar graph on a given set of points is, in general, NP-hard [Cab06]. Since
outerplanar graphs are the largest class of graphs ad mitt in g a straight-line point-set em-
bedding on every set of points [GMPP91] in general position, Kaufmann and Wiese [KW02]
investigate the