A Separator Theorem for Planar Graphs.

Abstract

Let G be any n-vertex planar graph. Prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than 2n/3 vertices, and C contains no more than 2(sq.rt 2)(sq. rt n) vertices. An algorithm is exhibited which finds such a partition A, B, C in o(n) time.

Open PDF

Document Details

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

Entities

People

  • Richard J. Lipton
  • Robert Tarjan

Organizations

  • Stanford University

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Boundaries
  • Computer Science
  • Computers
  • Embedding
  • Finite Element Analysis
  • Iterations
  • Military Research
  • Numerical Analysis
  • Scanning
  • Separators
  • Trees (Data Structures)
  • Triangles
  • Two Dimensional
  • United States
  • United States Government

Fields of Study

  • Mathematics

Readers

  • Graph Algorithms and Convex Optimization.