On cleaving a planar graph

DOI10.1016/0012-365X(90)90183-IMaRDI QIDQ917567zbMATH OpenFDO

Authors Shankar M. Venkatesan

Publication date 1990

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365X(90)90183-I

zbMATH Keywords

planar graphsseparationvertex weights

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10)

Review text

Let G be a planar n-vertex graph with non-negative vertex weights which sum to no more than 1. It is proved that G can be recursively separated into components of weight \(\leq \epsilon\) by removing \(4\sqrt{n/\epsilon}\) vertices. Applications to planar graphs with given radius are considered.

Recommendations

• Planar Separators
• scientific article; zbMATH DE number 867693
• scientific article; zbMATH DE number 1979709
• Reduced constants for simple cycle graph separation
• Weighted graph separators and their applications

Cites work

• A Separator Theorem for Planar Graphs
• Applications of a Planar Separator Theorem
• scientific article; zbMATH DE number 3815696 (Why is no real title available?)
• Improved constants for some separator theorems
• Partitioning planar graphs with vertex costs: Algorithms and applications

Cited in

(4)

• Finding the closed partition of a planar graph
• On splitting the Clebsch graph
• Obtaining a planar graph by vertex deletion
• Planarizing graphs and their drawings by vertex splitting

This page was built for publication: On cleaving a planar graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q917567)