# How to determine if a graph is two-connected?

3 views (last 30 days)

Show older comments

##### 0 Comments

### Answers (1)

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
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
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.

### See Also

### Categories

### Community Treasure Hunt

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

Start Hunting!