Accession Number:

ADA048787

Title:

Applications of a Planar Separator Theorem.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1977-10-01

Pagination or Media Count:

36.0

Abstract:

Any n-vertex planar graph has the property that it can be divided into components of roughly equal size by removing only Osquare 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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE