An Efficient Planarity Algorithm,

Abstract

An efficient algorithm is presented for determining whether a graph G can be embedded in the plane. Depth-first search, or backtracking, is the most important of the techniques used by the algorithm. If G has V vertices, the algorithm requires O(V) space and O(V) time when implemented on a tandom access computer. An implementation on the Stanford IBM 360/67 successfully analyzed graphs with as many as 900 vertices in less than 12 seconds. (Author)

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1971
Accession Number
AD0738027

Entities

People

  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Computers

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Graph Algorithms and Convex Optimization.
  • Parallel and Distributed Computing.

Technology Areas

  • Space
  • Space - Space Objects
  • Space - Spacecraft Maneuvers