# Vertex coloring for bi-connected components

In graph theory, a bi-connected component is a maximal bi-connected subgraph of a graph $g$—i.e., a connected subgraph that would remain connected if any one of its vertexes were to be removed. An articulation vertex (or cut vertex) of $g$ is a vertex which, if removed, increases the number of connected components in $g$. (Think of an articulation vertex as the only vertex linking two separate maximal subgraphs of $g$.)

A biconnected graph has no articulation vertices (for the subgraph), but an articulation vertex in $g$ can belong to several subgraphs, as illustrated in the figure here (from Wikipedia).

Consider all vertexes with any red. They form a connected subgraph and if you eliminate any of the red vertexes, the remaining red vertexes remain connected. (Moreover, the vertexes with red are the maximal set having this property, i.e., you can't color any more vertexes "red" and ensure this property.) Likewise for green and for all the other colors.

But look at the cut vertexes (which have pie diagrams) for instance the red/light-blue vertex. If you eliminate it, the number of connected components of the full graph $g$ (1) increases by one (to 2) as the red subgraph is "cut" from the graph. Likewise for all such pie-colored vertexes.

One can find the components and cut vertices of $g$ as shown here:

components = KVertexConnectedComponents[g, 2];
cutVertices = Flatten[Intersection @@@ Subsets[components, {2}]];


I would like to color the vertexes in an arbitrary undirected graph $g$ according to the bi-connected components, i.e., a separate color for each such component. But I'd like to go farther and color a cut vertex by a tiny pie chart with colors according to its bi-connected components.

How might one do that?

Update: A more flexible approach to specify the vertex shapes based on given properties of vertices:

ClearAll[vShapeF, colorsF1, colorsF2, kvccF, componentsF, neighborsF]

vShapeF[cedf_ : ChartElementDataFunction["TriangleWaveSector",
"AngularFrequency" -> 14, "RadialAmplitude" -> 0.09],
o : OptionsPattern[]][g_, df_, colf_ ] = Inset[
PieChart[ConstantArray[1, {Length[df[g, #2]]}],
ChartStyle -> colf[g, #2], ImageSize -> 60,
ChartElementFunction -> cedf, o, SectorOrigin -> {{Pi/4}, 1}], #] &;

kvccF[g_] := KVertexConnectedComponents[g, 2];
componentsF[g_, v_] := Select[Range[Length@kvccF[g]],
Function[{x}, MemberQ[kvccF[g][[x]], v]]]
colorsF1[col_ : ColorData[97, "ColorList"]][g_, v_] := col[[componentsF[g, v]]]

neighborsF[g_, v_] := Rest@VertexComponent[g, v, 1]

colorsF2[col_ : ColorData[97, "ColorList"]][g_, v_] :=
Blend[{col[[v]], Black}, #] & /@ (Rescale[Range[0, Length@neighborsF[g, v]]]/2)


Examples:

edges = {1 <-> 2, 1 <-> 3, 2 <-> 4, 3 <-> 4, 4 <-> 5, 5 <-> 6,
6 <-> 7, 7 <-> 8, 7 <-> 9, 7 <-> 13, 9 <-> 11, 9 <-> 10,
11 <-> 12, 12 <-> 13, 13 <-> 14};
options = Sequence[GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Left},
VertexLabels -> Placed["Name", Center],
VertexLabelStyle -> Directive[Bold, 16] , ImageSize -> 700];

g = Graph[edges, options];


Vertex shape as a pie-chart based on the components to which the vertex belongs:

SetProperty[g, VertexShapeFunction -> vShapeF[][g, componentsF, colorsF1[]]]


In the next example,the number of pie pieces and the colors are based on the number of immediate neighbors (each vertex has its own color and different pieces of the PieChart are based on that color and the number of neighbors):

SetProperty[g, {VertexShapeFunction -> vShapeF[][g, neighborsF, colorsF2[]]}]


Each vertex has its own color and different pieces of the pie are colored as a blend of own color and neighbor's color:

colorsF3[col_ : ColorData[97, "ColorList"]][g_, v_] :=
Prepend[Blend[{col[[v]], col[[#]]}, 1/2] & /@ neighborsF[g, v],
Directive[EdgeForm[{Thick, Opacity[1], Black}], col[[v]]]]

SetProperty[g, {VertexShapeFunction->vShapeF[][g, VertexComponent[##, 1] &, colorsF3[]]}]


A different input graph:

gb = EdgeAdd[g, {7 <-> 1, 7 <-> 3, 12 <-> 14, 11 <-> 14}];

SetProperty[gb, VertexShapeFunction -> vShapeF[][gb, componentsF, colorsF1[]]]


SetProperty[gb, {VertexShapeFunction -> vShapeF[][gb, neighborsF, colorsF2[]]}]


SetProperty[gb, {VertexShapeFunction->vShapeF[][gb, VertexComponent[##, 1] &, colorsF3[]]}]


Finally, the previous example with non-default arguments

SetProperty[gb, {VertexShapeFunction ->
vShapeF[ChartElementDataFunction["NoiseSector",
"AngularFrequency" -> 5, "RadialAmplitude" -> 0.1]
, SectorOrigin -> {{Pi, -1}, 1}
][gb, VertexComponent[##, 1] &,
colorsF3[ColorData[54, "ColorList"]]]}]


ClearAll[cF, vsF]

edges = {1 <-> 2, 1 <-> 3,   2 <-> 4, 3 <-> 4, 4 <-> 5,   5 <-> 6,  6 <-> 7,   7 <-> 8,
7 <-> 9,   7 <-> 13, 9 <-> 11,   9 <-> 10, 11 <-> 12, 12 <-> 13, 13 <-> 14};

g = Graph[edges];
components = KVertexConnectedComponents[g, 2];


Define a function cF to assign color(s) to vertices based on the components a vertex belongs:

colors = ColorData[95, "ColorList"][[ ;; Length@components]];
(cF[#] = colors[[Select[Range[Length@components], Function[{x},
MemberQ[components[[x]], #]]]]]) & /@ VertexList[g];


Define a custom VertexShapeFunction to produce PieCharts using as input the set of components a vertex belongs and the associated colors:

cedf = ChartElementDataFunction["TriangleWaveSector", "AngularFrequency" -> 14,
vsF = Inset[  PieChart[ConstantArray[1, {Length[cF@#2]}],
ChartStyle -> cF[#2], ImageSize -> 60, ChartElementFunction -> cedf,
SectorOrigin -> {{Pi/4}, 1}], #] &;


Use vsF with Graph:

Graph[edges, VertexShapeFunction -> vsF,
GraphLayout -> {"LayeredDigraphEmbedding", "Orientation" -> Left},
VertexLabels -> Placed["Name", Center],
VertexLabelStyle -> Directive[Bold, 16] , ImageSize -> 700]


• Orientation of colors of the pie pieces needs additional work.
– kglr
Jun 28, 2017 at 4:31
• Very nice, and fast work. (I personally don't like the "NoiseSector" chart element, but that is easy to fix.) The orientation of colors will be rather difficult, since it will rely on the graph layout. Nevertheless: accepted. Jun 28, 2017 at 4:52
• Thank you @DavidG.Stork for the accept. Good question.
– kglr
Jun 28, 2017 at 4:53

Not a direct answer, just a practical suggestion. When visualizing biconnected components, it may be more useful to colour edges, not vertices. A vertex may belong to multiple biconnected components, but an edge always belong to a single one.

This is the graph from your post (entered conveniently using IGShorthand from IGraph/M, but I won't show that here to avoid dependency on a package).

g = Graph[{1 \[UndirectedEdge] 2, 2 \[UndirectedEdge] 3,
3 \[UndirectedEdge] 4, 1 \[UndirectedEdge] 4,
4 \[UndirectedEdge] 5, 5 \[UndirectedEdge] 6,
6 \[UndirectedEdge] 7, 7 \[UndirectedEdge] 8,
8 \[UndirectedEdge] 9, 9 \[UndirectedEdge] 10,
10 \[UndirectedEdge] 11, 7 \[UndirectedEdge] 11,
11 \[UndirectedEdge] 12, 10 \[UndirectedEdge] 12,
7 \[UndirectedEdge] 13, 8 \[UndirectedEdge] 14}]

HighlightGraph[
Graph[g, GraphStyle -> "ThickEdge", EdgeStyle -> Opacity[.5]],
EdgeList@Subgraph[g, #] & /@ KVertexConnectedComponents[g, 2],