An Efficient Planarity Algorithm

Front Cover
Department of Computer Science, Stanford University, 1971 - Geometry, Plane - 154 pages
0 Reviews
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).

From inside the book

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

Introduction
2
Definitions from Graph Theory
8
h Data Structures Representing Graphs
23

10 other sections not shown

Other editions - View all

Bibliographic information