Decomposition of Graphs into Biconnected and Triconnected Components

Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
Producer
Director
Performer
Choreographer
Costume Designer
Music
Videographer
Lighting Designer
Set Designer
Crew Member
Funder
Rehearsal Director
Concert Coordinator
Moderator
Panelist
Alternative Title
Department
Haverford College. Department of Computer Science
Type
Thesis
Original Format
Running Time
File Format
Place of Publication
Date Span
Copyright Date
Award
Language
eng
Note
Table of Contents
Terms of Use
Rights Holder
Access Restrictions
Dark Archive
Tripod URL
Identifier
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.
Description
Citation
Collections