Initialization

Needs["Notation`"];
InfixNotation[(NotationTemplateTag[∈]),MyElement];
InfixNotation[(NotationTemplateTag[∉]),NotMyElement];

(* General Utils *)
MyElement[a:Except[_Symbol],b_List]:=MemberQ[b,a];
NotMyElement[a_,b_List]:=Not[MyElement[a,b]];
Tilde[x__]:=Join[x];
Subset[a_List,b_List]:=(a⋂b==a)
NotSubset[a_List,b_List]:=Not[Subset[a,b]];
Backslash[a_List,b_List]:=(Complement[a,b]);
BracketingBar[a_List]:=Length[a];

fl1[lst_]:=Flatten[lst,1];
pos1[lst_,item_]:=Position[lst,item][[1,1]];
disjoint[A_,B_]:=Length[A⋂B]==0;
intersect[a_,b_]:=Select[a,MemberQ[b,#]&];


AllTrue[{var_Symbol,lis_List},expr_]:=LengthWhile[lis,TrueQ[ReleaseHold[Hold[expr]/.HoldPattern[var]->#]]&]==Length[lis];
AnyTrue[{var_Symbol,lis_List},expr_]:=LengthWhile[lis,Not[TrueQ[ReleaseHold[Hold[expr]/.HoldPattern[var]->#]]]&]<Length[lis];
myTable[{var_Symbol,vals_List},expr_]:=ReleaseHold[Hold[expr]/.HoldPattern[var]->#]&/@vals;

(* Parts used for tree building *)

connComps[v_]:=ConnectedComponents[Subgraph[g,v]]
isRedundant[bag_]:=AnyTrue[{b,bags},b≠bag∧bag⊂b];
touchingVerts[v_List]:=VertexList[NeighborhoodGraph[g,v]]∖v;
touchingVerts[v_Integer]:=touchingVerts[{v}];

elim[v_]:=(
If[v∈elimed,Return[]];
comps=connComps[V∖elimed];
ourComp=Select[comps,v∈#&]//First;
boundary=touchingVerts[ourComp];
AppendTo[bags,boundary⋃{v}];
elimed=elimed⋃{v};
bags=Select[bags,Not[isRedundant[#]]&];
);

(* gets all pairs of sets that intersect *)
intersectingPairs[bags_List]:=Module[{cands,result},
cands=Outer[List,bags,bags,1]//fl1;
Select[cands,#[[1]]≠#[[2]]&&!disjoint[#[[1]],#[[2]]]&&OrderedQ[#]&]
];

(* maximum spanning tree *)
makeSpanningTree[bags_]:=Module[{jtree,edgeCandidates,bestEdge,lens},
acyclicEdges[ed_]:=
Select[ed,AcyclicGraphQ[Graph[UndirectedEdge@@@(jtree∼{#})]]&];

findHeaviestEdge[ed_]:=(
lens=\[LeftBracketingBar]#[[1]]⋂#[[2]]\[RightBracketingBar]&/@ed;
If[lens=={},{},ed[[Last@Ordering@lens]]]
);

(* adds pair of bags with largest intersection to tree, removes cyclical candidates *)
growTree[]:=(
bestEdge=findHeaviestEdge[edgeCandidates];
jtree=jtree∼{bestEdge};
edgeCandidates=edgeCandidates∖{bestEdge};
edgeCandidates=acyclicEdges[edgeCandidates];
);
edgeCandidates=intersectingPairs[bags];
jtree={};
While[edgeCandidates≠{},growTree[]];
Sort[jtree]
];

(** Visualization Utils **)
initGraph[graphName_]:=(
(* initializing graph *)
(*g=CycleGraph[8,VertexShapeFunction->shapeFunc];
g=Graph[{1\[UndirectedEdge]2,2\[UndirectedEdge]3,2\[UndirectedEdge]9,5\[UndirectedEdge]4,3\[UndirectedEdge]4,4\[UndirectedEdge]8,1\[UndirectedEdge]5,5\[UndirectedEdge]6,6\[UndirectedEdge]7,5\[UndirectedEdge]10,10\[UndirectedEdge]7,7\[UndirectedEdge]8,9\[UndirectedEdge]4},VertexShapeFunction->shapeFunc];*)
(* initializing Graphics *)
masterScale=100;
lineThickness=.5;
vertSize=1/2;

g=GraphData[graphName];
vcoords=Thread[VertexList[g]->(VertexCoordinates/.AbsoluteOptions[g,VertexCoordinates])];
(*g=GridGraph[{3,3},VertexShapeFunction->shapeFunc];*)
gg=Graph[EdgeList[g],VertexCoordinates->vcoords,VertexShapeFunction->shapeFunc];
V=VertexList[g];
elimed={};
bags={};

graphPR=getPlotRange[V/.vcoords];
graphPR=correctPR[graphPR,masterScale];
graphIS=-masterScale Subtract@@@graphPR;
graphStyle="DiagramBlack";
colorList=ColorData["Atoms","ColorList"];
);

correctPR[pr_,scale_]:={pr[[1]]+{-1/scale,2/scale},pr[[2]]+{-2/scale,1/scale}};
getPlotRange[lst_]:=({xs,ys}=Transpose[lst];
(*two extra 1/scale offsets needed for exact match*){{Min[xs]-lineThickness/2,Max[xs]+lineThickness/2+1/masterScale},{Min[ys]-lineThickness/2-1/masterScale,Max[ys]+lineThickness/2}}
);

vertexClick[v_]:=(
Print["eliminating ",v];
elim[v];
);

(* regular ymin-1,xmax+1, and addition 1 pixel for antialiasing *)
makeVertex[{x_,y_},v_]:=(
plotRange=Transpose[{{x,y}-vertSize/2,{x,y}+vertSize/2}];
plotRange=correctPR[plotRange,masterScale];
imageSize=-masterScale Subtract@@@plotRange;
button={Transparent,EdgeForm[Thick],Button[Disk[{x,y},vertSize/2],vertexClick[v]]};
label={Black,Style[Text[v,{x,y}],Bold,14]};
label∼button
);
shapeFunc[{x_,y_},v_,{w_,h_}]:=makeVertex[{x,y},v];

drawBag[bag_List,scale_:masterScale]:=(
bagGraph=Subgraph[g,bag,VertexCoordinates->vcoords,GraphStyle->graphStyle];
tileEnds=Select[Outer[List,bag,bag]//fl1,#[[1]]≤#[[2]]&];
tiles=FindShortestPath[CompleteGraph[Length[V]],#[[1]],#[[2]]]&/@tileEnds;

bagColor=Extract[colorList,Position[nrBags,bag]]//First;
tileOpts={bagColor,AbsoluteThickness[lineThickness*scale],CapForm["Round"],JoinForm["Round"],Opacity[.8]};
allPoints=Flatten[tiles/.vcoords,1];
plotRange=getPlotRange[allPoints];
imSize=-scale*Subtract@@@plotRange;

tileG=Graphics[tileOpts~Join~ (Line[#/.vcoords]&/@tiles),PlotRange->plotRange,ImageSize->imSize]
);

drawBags[]:=(
nrBags=Select[bags,Not[isRedundant[#]]&];
Show[Sequence@@(drawBag/@nrBags),gg,PlotRange->graphPR,ImageSize->graphIS]
);



drawGraphFragment[bag_,scale_:masterScale]:=(
bagGraph=Subgraph[g,bag];
allPoints=bag/.vcoords;
plotRange=getPlotRange[allPoints];
imSize=-scale*Subtract@@@plotRange;

Subgraph[g,bag,PlotRange->plotRange,GraphStyle->"SimpleLink",EdgeStyle->Transparent,ImageSize->imSize,VertexCoordinates->vcoords]
);

visGraph[]:=Module[{},
(* maximum spanning tree *)
nrBags=Select[bags,!isRedundant[#]&];
jtree=makeSpanningTree[nrBags];
bagCentroid[bag_]:=Mean[bag/.vcoords];

findExtremeBag[vec_]:=(
vertList=First/@vcoords;
coordList=Last/@vcoords;
goodBags=DeleteCases[bags,{}];
extremePos=First[Ordering[goodBags,1,bagCentroid[#1].vec>bagCentroid[#2].vec&]];
goodBags[[extremePos]]
);


extremeDirs={{1,1},{1,-1},{-1,1},{-1,-1}};
extremeBags=findExtremeBag/@extremeDirs;
extremePoses=bagCentroid/@extremeBags;

(*** Show bags as vertices of another GraphPlot ***)
scale=50;
GraphPlot[Rule@@@jtree,
VertexRenderingFunction->(Inset[Show[drawBag[#2,scale],drawGraphFragment[#2,scale]],#]&),
EdgeRenderingFunction->({Gray,Thick,Arrowheads[.0],Arrow[#1,.0]}&),
VertexCoordinateRules->Thread[Thread[extremeBags->extremePoses]],
PlotRange->graphPR,
ImageSize->1.5graphIS
]
];

showGraphs[n_,cl__]:=Module[{k=6},
graphs=getGraphs[n,cl];
Print["Total: ",Length[graphs]];
graphs=graphs[[;;Min[(k^2),Length[graphs]]]];
GraphicsGrid[Partition[Tooltip[GraphData[#],#]&/@graphs,k],ImageSize->400]
]

getGraphs[n_,cl__]:=getGraphs[{n,n},cl];
getGraphs[{nmin_,nmax_},cl__]:=Module[{maxgraphnum=100},
classes={cl}∖customClasses;
Assert[classes⊂GraphData["Classes"]];
customClasses={"isLeafFree",!"isLeafFree"};
isLeafFree[gname_]:=FreeQ[GraphData[gname,"DegreeSequence"],0|1];

posClasses=Cases[classes∖customClasses,_String];
posGroup=If[posClasses=={},GraphData[nmin;;nmax],GraphData[posClasses,nmin;;nmax]];
negClasses=classes∖posClasses;
negGroups=GraphData[#[[1]],nmin;;nmax]&/@negClasses;

result=Complement[posGroup,Sequence@@negGroups];
customTest[g_]:=And@@(ToExpression[#][g]&/@({cl}⋂customClasses));
(*result=Take[result,Min[Length[result],100]];*)

result=Select[result,customTest]
]

Main

showGraphs[8,"Planar","isLeafFree","Bridgeless","Connected"]

initGraph[{"Polyiamond",{6,12}}]
Dynamic[drawBags[],TrackedSymbols:>{bags}]

visGraph[]

initGraph[{"Grid",{3,3}}]
Dynamic[drawBags[],TrackedSymbols:>{bags}]

visGraph[]