Need "bulatov" packages, also check blog - chordal and clusterVisualize.nb for cluster visualization

twoColorGraph[vals1_,vals2_,g_Graph]:=(
verts=VertexList@g;
edges=EdgeList@g;
vcoords=graphCoords@g;
vf[{xc_,yc_},name_,{w_,h_}]:=(
d1=Disk[{xc,yc},Max[w,h],{0,Pi}];
d2=Disk[{xc,yc},Max[w,h],{Pi,2Pi}];
{ColorData["Crayola"]["NavyBlue"],Opacity[vals1[[name]]],d1,Opacity[vals2[[name]]],d2}
);
Graph[verts,UndirectedEdge@@@edges,VertexShapeFunction->vf,VertexSize->{"Scaled",.1},VertexCoordinates->vcoords]
);

threeClassGraph[g_Graph,gr1_,gr2_,label_]:=(
verts=VertexList@g;
edges=EdgeList@g;
vcoords=graphCoords@g;
vf[{xc_,yc_},name_,{w_,h_}]:=(
d=Which[
MemberQ[gr1,name],{ColorData["Crayola"]["NavyBlue"],Disk[{xc,yc},Max[w,h]]},
MemberQ[gr2,name],{LightGray,EdgeForm[{Thick,Dashing[.03]}],Disk[{xc,yc},Max[w,h]]},
True,{White,Disk[{xc,yc},Max[w,h]]}
]
);

Graph[verts,UndirectedEdge@@@edges,VertexShapeFunction->vf,VertexSize->{"Scaled",.1},VertexCoordinates->vcoords,PlotLabel->label,ImageSize->{150,150}]
);

g=CompleteKaryTree[3]

pic1=threeClassGraph[g,{},Range@7,Style["41",20]]
pic2=threeClassGraph[g,{},{2,3,4,5,6,7},Style["25",20]]
pic3=threeClassGraph[g,{1},{2,3,4,5,6,7},Style["16",20]]

Row[{pic1,Style["=",40],pic2,Style["+",40],pic3}]

pic4=threeClassGraph[g1,{},{2,4,5},Style["5",20]]//Show
pic5=threeClassGraph[g2,{},{3,6,7},Style["5",20]]//Show

Row[{pic2,Style["=",40],pic4,Style["×",40],pic5}]

g3=GridGraph[{3,2}];

ppp=threeClassGraph[g3,{},Range[6],Style["17",30]]

graphs=Show[threeClassGraph[g3,#,{1,3,4,6},""]]&/@Subsets[{2,5}];

Row@Riffle[graphs,Style["+",50]]

graphs=Show[threeClassGraph[g3,#,{1,3,4,6}]]&/@Subsets[{2,5}]

counts={9,4,4,0};
graphs=MapIndexed[Show@threeClassGraph[g3,#1,{1,3,4,6},Style[counts[[#2[[1]]]],20]]&,Subsets[{2,5}]]

Row@({ppp,Style["=",30]}~Join~Riffle[graphs,Style["+",30]])

Needs["Bulatov`chordal`"]

g=medusaGraph[3,6]//changeGraphStyle[#,Automatic]&

g=;

makeChordalGraph[g,1]

graphs2={g}~Join~(makeChordalGraph[g,#]&/@Range[2,4])

Show[graphs2[[#]],PlotLabel->"treewidth="~~ToString[#]]&/@Range[4]

Cluster graph

SetDirectory[NotebookDirectory[]];
Needs["Bulatov`common`","Bulatov`chordal`"];
vcoords={1->{0,6},2->{6,0},3->{3,6},4->{3,2},5->{3,0},6->{5.8,4},7->{6,6},8->{0,4},9->{0,0},10->{6,2}};
edges=UndirectedEdge@@@{1->3,1->8,2->5,2->10,3->7,4->9,4->10,5->9,6->7,6->8,6->10,8->9,8->10};
fillEdges=UndirectedEdge@@@{3->8,5->10,7->8,7->10,9->10};
g=Graph[edges,VertexCoordinates->vcoords,GraphStyle->"DiagramBlack"];
n=Length@VertexList@g;

g=relabelGraph[g,Range[n]];
mat=Normal@AdjacencyMatrix[g];

diag=IdentityMatrix[n];
um=Array[Boole[#2>#1]&,{n,n}];


tg=Graph[edges∼fillEdges,VertexCoordinates->vcoords,GraphStyle->"DiagramBlack"];
tg=relabelGraph[tg,Range[n]];

tg2=relabelGraph[tg,Reverse@VertexList@tg]

repl=Thread[Range[10]->Reverse[Range@10]]

decomp2=decomp/.repl

initGraph@tg;
{jnodes,jedges}=decomp2;
temp=makeClusterGraph[tg,decomp2,1]

GraphPlot

tg2