BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-628
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Applications of a planar separator theorem
        TYPE:: Technical Report
      AUTHOR:: Lipton, Richard J.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: October 1977
       PAGES:: 36
    ABSTRACT:: Any n-vertex planar graph has the property that it can be
               divided into components of roughly equal size by removing
               only O($\sqrt{n}$) vertices. This separator theorem, in
               combination with a divide-and-conquer strategy, leads to many
               new complexity results for planar graph problems. This paper
               describes some of these results.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-628