On approximating a vertex cover for planar graphs

1982/05/05 by Reuven Bar-Yehuda, Shimon Even · 49 citations
Computer Science · Mathematics · Engineering · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Vertex cover #Planar #Vertex (graph theory) #Cover (algebra) #Planar graph #Computer science #Combinatorics #Planar straight-line graph #Mathematics #Graph #1-planar graph #Chordal graph #Engineering #Computer graphics (images)

paper · pdf · doi:10.1145/800070.802205

openalex publication_date 1982/05/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

The approximation problem for vertex cover of n-vertex planar graphs is treated. Two results are presented:

Citations

• Applications of a Planar Separator Theorem
• Finding a Minimum Circuit in a Graph
• Depth-First Search and Linear Graph Algorithms

Cited by

• Planar separator theorem [wikipedia]