2023/12/13 by Brandon Du Preez, Preez, Brandon Du
Computer Science · #05C40 (Primary) 05C10 #05C85 #68R10 (Secondary) #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.2 #Graph Labeling and Dimension Problems
paper · pdf · doi:10.48550/arxiv.2312.08355
openalex publication_date 2023/12/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let G=(V,E) be a connected graph. A subset S⊂ V is a cut of G if G-S is disconnected. A near triangulation is a 2-connected plane graph that has at most one face that is not a triangle. In this paper, we explore minimal cuts of 4-connected planar graphs. Our main result is that every minimal cut of a 4-connected planar graph G is connected if and only if G is a near-triangulation. We use this result to sketch a linear-time algorithm for finding a disconnected cut of a 4-connected planar graph.