Planarity Testing in V Log V Steps: Extended Abstract,

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)

Document Details

Document Type
Technical Report
Publication Date
Feb 01, 1971
Accession Number
AD0722434

Entities

People

  • John Hopcroft
  • Robert Tarjan

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Boundaries
  • Computations
  • Computers
  • Mathematical Analysis
  • Mathematics

Readers

  • Computer Science/Computer Engineering/Data Science/Digital Signal Processing.
  • Graph Algorithms and Convex Optimization.

Technology Areas

  • Space
  • Space - Spacecraft Maneuvers