BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-77-627
       ENTRY:: June 28, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: A separator theorem for planar graphs
        TYPE:: Technical Report
      AUTHOR:: Lipton, Richard J.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: October 1977
       PAGES:: 34
    ABSTRACT:: Let G be any n-vertex planar graph. We prove that the
               vertices of G can be partitioned into three sets A,B,C such
               that no edge joins a vertex in A with a vertex in B, neither
               A nor B contains more than 2n/3 vertices, and C contains no
               more than $2\sqrt{2}\sqrt{2}$ vertices. We exhibit an
               algorithm which finds such a partition A,B,C in O(n) time.
       NOTES:: [Adminitrivia V1/Prg/19950628]
         END:: STAN//CS-TR-77-627