Accession Number:

ADA048786

Title:

A Separator Theorem for Planar Graphs.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CALIF DEPT OF COMPUTER SCIENCE

Personal Author(s):

• Lipton,Richard J.
• Tarjan,Robert E.

Report Date:

1977-10-01

Pagination or Media Count:

33.0

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 2n3 vertices, and C contains no more than 2sq.rt 2sq. rt n vertices. An algorithm is exhibited which finds such a partition A, B, C in on time.

Descriptors:

• *GRAPHS
• *COMBINATORIAL ANALYSIS
• ALGORITHMS
• CIRCUIT ANALYSIS
• BOOLEAN ALGEBRA
• CONVOLUTION
• DISSECTION

Subject Categories:

• Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE