Embedding an outer-planar graph in a point set
Andrew King
Project for CS507, Computational Geometry
December 20, 2004
The problem:
Graph drawing, a field of mathematics that blends computational geometry and graph theory, is often concerned with finding a "good" embedding of a graph in a topological surface, generally the plane. In this instance, however, we wish to embed a graph in a given two-dimensional point set using only non-crossing straight lines for edges.
Given an outer-planar graph G and a point set P, we want an efficient algorithm for creating a straight-line embedding of G in P.
This web page provides some background on the problem and proceeds to outline an efficient algorithm, courtesy of Prosenjit Bose, for embedding outer-planar graphs in point set [B02]. The algorithm runs in wost case O(n2) time and best case O(n log n) time, depending on the structure of the graph.
In computational geometry, problems generally have input restrictions to prevent troublesome cases. In this instance, we simply demand that the point set contains no three points on a line.