How to determine if a graph is two-connected?

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!

Answer 1

[Christine Tobler]

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.

[Ephraim Bryski]

I think biconconncomp() returns a vector of ones if it is 3-connected or 4-connected or any number greater than 1 though. For example:

s = [1 1 1 2 4 2 5 2 3 3 4];
t = [2 4 6 4 6 5 6 3 5 6 5];
G = graph(s,t);
p = plot(G);
bins = biconncomp(G);

Also, how would I get the graphs it can be separated into by removing 2 nodes (not 1)?

I think my question might have been unclear.

[Image Analyst]

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]

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.