2016/02/14 by Martin Grohe, Grohe, Martin
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1602.04505
openalex publication_date 2016/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We introduce a new decomposition of a graphs into quasi-4-connected components, where we call a graph quasi-4-connected if it is 3-connected and it only has separations of order 3 that remove a single vertex. Moreover, we give a cubic time algorithm computing the decomposition of a given graph. Our decomposition into quasi-4-connected components refines the well-known decompositions of graphs into biconnected and triconnected components. We relate our decomposition to Robertson and Seymour's theory of tangles by establishing a correspondence between the quasi-4-connected components of a graph and its tangles of order 4.