Applications of a Planar Separator Theorem.

Abstract

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only O(square root of n) vertices. This separator theorem, in combination with a divide-and-conquer strategy, leads to many new complexity results for planar graph problems. This paper describes some of these results. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1977
Accession Number
ADA048787

Entities

People

  • Richard J. Lipton
  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms
  • C4I

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computational Complexity
  • Computer Programming
  • Computer Science
  • Computers
  • Dynamic Programming
  • Embedding
  • Military Research
  • New York
  • Security
  • Separators
  • Trees (Data Structures)
  • United States
  • Universities

Readers

  • Graph Algorithms and Convex Optimization.