How to determine if a graph is two-connected?

5 views (last 30 days)
Hi. I have a graph in MATLAB and I would like to determine if it is two-connected. I would also like to have the graphs which it can be separated into as outputs. Is there a way of doing this efficiently in MATLAB, either using built-in functionality, or writing code? Thanks!

Answers (1)

Christine Tobler
Christine Tobler on 11 Jan 2021
The biconncomp function will split the edges of a graph into its biconnected components. If the output of biconncomp is a vector of all ones, that graph is two-connected.
Otherwise, here's some code that will extract each biconnected component as an individual graph as follows:
s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
p = plot(G);
bins = biconncomp(G);
for binNr = 1:max(bins)
st = G.Edges.EndNodes;
Gbin = subgraph(G, unique(st(bins == binNr, :)));
figure;
plot(Gbin)
end
Keep in mind: For a graph without node names in MATLAB, nodes are numbered through 1, 2, ..., [number of nodes]. This means that the subgraph command can assign a new node index (e.g., if G has three nodes, subgraph(G, [1 3]) will return a graph where the previous node 3 is now node 2). You can avoid this by using node names.
  3 Comments
Image Analyst
Image Analyst on 11 Jan 2021
Visualization (for other people):
s = [1 1 2 2 3 4 4 5 6 6 7 7 8];
t = [2 3 3 4 4 5 7 6 7 10 8 9 9];
G = graph(s,t);
subplot(2, 3, 1);
p = plot(G);
bins = biconncomp(G);
for binNr = 1:max(bins)
st = G.Edges.EndNodes;
Gbin = subgraph(G, unique(st(bins == binNr, :)));
subplot(2, 3, binNr + 1);
plot(Gbin)
caption = sprintf('Bin #%d', binNr);
title(caption, 'FontSize', 15);
end
g = gcf;
g.WindowState = 'maximized';
Christine Tobler
Christine Tobler on 12 Jan 2021
If a graph is 3- or 4- connected, this means it is also two-connected (biconnected). The biconncomp function only answer the question of whether a graph is two-connected or how it can be split into biconnected components.
MATLAB doesn't have functionality for computing k-connectivity except for k=1 (conncomp) and k=2 (biconncomp). For the 3-connected case I think you're looking for, a quick wikipedia search suggests you might need to look at the concept of SPQR trees. An algorithm is described on that page, with reference to papers for details.

Sign in to comment.

Categories

Find more on Graph and Network Algorithms in Help Center and File Exchange

Products


Release

R2020b

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!