BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-71-201
       ENTRY:: November 01, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Planarity testing in V log V steps: extended abstract
        TYPE:: Technical Report
      AUTHOR:: Hopcroft, John E.
      AUTHOR:: Tarjan, Robert Endre
        DATE:: February 1971
       PAGES:: 24
    ABSTRACT:: An efficient algorithm is presented for determining whether
               or not a given graph is planar. If V is the number of
               vertices in the graph, the algorithm requires time
               proportional to V log V and space proportional to V when run
               on a random-access computer. The algorithm constructs the
               facial boundaries of a planar representation without backup,
               using extensive list-processing features to speed
               computation. The theoretical time bound improves on that of
               previously published algorithms. Experimental evidence
               indicates that graphs with a few thousand edges can be tested
               within seconds.
       NOTES:: [Adminitrivia V1/Prg/19951101]
         END:: STAN//CS-TR-71-201