Advertisement
Published in:
2010 | OriginalPaper | Chapter
Why Depth-First Search Efficiently Identifies Two and Three-Connected Graphs
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Given an undirected 3-connected graph
G
with
n
vertices and
m
edges, we modify depth-first search to produce a sparse spanning subgraph with at most 4
n
− 10 edges that is still 3-connected. If
G
is 2-connected, to maintain 2-connectivity, the resulting graph will have at most 2
n
− 3 edges. The way depth-first search discards irrelevant edges illustrates the reason behind its ability to verify and certify biconnectivity [1,2,3] and triconnectivity [4,5] in linear time. Dealing with a sparser graph, after the first depth-first-search calls, makes the algorithms in [2,5] more efficient. We also give a characterization of separation pairs of a 2-connected graph in terms of the resulting sparse graph.