Report Number: CS-TR-81-876
Institution: Stanford University, Department of Computer Science
Title: On linear area embedding of planar graphs
Author: Dolev, Danny
Author: Trickey, Howard W.
Date: September 1981
Abstract: Planar embedding with minimal area of graphs on an integer
grid is one of the major issues in VLSI. Valiant [1981] gave
an algorithm to construct a planar embedding for trees in
linear area; he also proved that there are planar graphs that
require quadratic area.
We give an algorithm to embed outerplanar graphs in linear
area. We extend this algorithm to work for every planar graph
that has the following property: for every vertex there
exists a path of length less than K to the exterior face,
where K is a constant.
Finally, finding a minimal embedding area is shown to be
NP-complete for forests, and hence for more general types of
graphs.
http://i.stanford.edu/pub/cstr/reports/cs/tr/81/876/CS-TR-81-876.pdf