Accession Number : AD0722434

Title :   Planarity Testing in V Log V Steps: Extended Abstract,

Corporate Author : STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s) : Hopcroft,John ; Tarjan,Robert

Report Date : FEB 1971

Pagination or Media Count : 20

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. (Author)

Descriptors :   (*COMPUTER PROGRAMMING, *GRAPHICS), ALGORITHMS, CHEMICAL BONDS, INTEGRATED CIRCUITS

Subject Categories : Theoretical Mathematics
      Computer Programming and Software
      Computer Hardware

Distribution Statement : APPROVED FOR PUBLIC RELEASE