Decomposition of Graphs into Biconnected and Triconnected Components

Abstract

One of the most fundamental concepts in graph theory is connectivity, or the property that a path exists between two vertices in a given graph. The property of connectivity may be extended into biconnectivity and triconnectivity, the property that there are two (biconnected) or three (triconnected) separate paths between two vertices. While not all graphs are connected, biconnected or triconnected, it is possible to decompose all graphs into the maximal components for which these properties hold. These are known as connected components, biconnected components and triconnected components of a graph. This thesis explores the algorithms that have been developed by graph theorists to perform biconnected and triconnected decomposition, specifically those designed to break a graph into vertex biconnected and vertex triconnected components. In addition, we provide specifications for biconnected decompositions in first-order logic.