Finding small simple cycle separators for 2-connected planar graphs

1986/06/01 by Gary L. Miller · 143 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Cycle basis #Discrete mathematics #Graph #Graph Labeling and Dimension Problems #Graph power #Line graph #Mathematics #Planar #Planar graph #Simple (philosophy) #Simple graph #Wheel graph

paper · pdf · doi:10.1016/0022-0000(86)90030-9

published in Journal of Computer and System Sciences 32(3), 265-279 (Elsevier BV)

crossref issued 1986/06/01 · crossref published 1986/06/01 · crossref published-print 1986/06/01 · openalex publication_date 1986/06/01 · crossref created 2003/12/04 · crossref deposited 2019/02/16 · openalex created_date 2025/10/10 · crossref indexed 2026/06/12 · openalex updated_date 2026/08/01

Citations

• Efficient Planarity Testing
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• A Separator Theorem for Planar Graphs
• Parallel Algorithms in Graph Theory: Planarity Testing

Cited by

• A Fixed-Parameter Algorithm for the Minimum Weight Triangulation Problem Based on Small Graph Separators
• Cycle bases in graphs characterization, algorithms, complexity, and applications
• Exact algorithms for the Hamiltonian cycle problem in planar graphs
• Edge separators for graphs of bounded genus with applications
• Moments of Inertia and Graph Separators
• Shortest paths in directed planar graphs with negative lengths
• A Fast General Methodology for Information-Theoretically Optimal Encodings of Graphs
• Disk packings and planar separators
• Planar separator theorem [wikipedia]