1982/06/01 by Hristo Djidjev · 99 citations
Computer Science · Engineering · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #VLSI and FPGA Design Techniques #Mathematics #Combinatorics #Planar graph #Planar #Graph #Upper and lower bounds #Set (abstract data type) #Discrete mathematics #Book embedding #Chordal graph #1-planar graph #Computer science
paper · doi:10.1137/0603022
published in SIAM Journal on Algebraic and Discrete Methods 3(2), 229-240 (Society for Industrial and Applied Mathematics)
openalex publication_date 1982/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2025/11/06
The results in this paper are closely related to the effective use of the divide-and-conquer strategy for solving problems on planar graphs. It is shown that every planar graph can be partitioned into two or more components of roughly equal size by deleting only O ( √(n) ) vertices, and such a partitioning can be found in O ( n ) time. Some of the theorems proved in the paper are improvements on the previously known theorems while others are of more general form. An upper bound for the minimum size of the partitioning set is found.