BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-81-876
       ENTRY:: June 05, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: On linear area embedding of planar graphs
        TYPE:: Technical Report
      AUTHOR:: Dolev, Danny
      AUTHOR:: Trickey, Howard W.
        DATE:: September 1981
       PAGES:: 24
    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.
       NOTES:: [Adminitrivia V1/Prg/19950605]
         END:: STAN//CS-TR-81-876