Planar Connected Graph

Author

Eric W. Weisstein
November 22, 2003

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/PlanarConnectedGraph.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PlanarConnectedGraph.html.

©2005 Wolfram Research, Inc. except for portions noted otherwise

Counts

Should be 1, 1, 1, 2, 6, 20, 99, 646, 5974, 71885, … (OEIS A003094)

Table[Count[ConnectedGraphs[n],_?PlanarQ],{n,8}]//Timing

Table[Count[ConnectedGraphs[n],_?PlanarQ],{n,9}]//Timing

Table[Count[PlanarGraphs[n],_?ConnectedQ],{n,9}]//Timing

Length/@PlanarConnectedGraphs/@Range[9]

Grapics

ShowGraphArray[Flatten[Partition[#,10,10,{1,1},{}]&/@PlanarConnectedGraphs/@Range[5],1],VertexStyle->Disk[.2]]

Planar Connected with minimum valency

sg[g_]:=showGraph[RecognizeGraph[g],PlotStyles->{PointSize[.12]}]

pc[1,i_]:=pc[i]
pc[n_,i_]:=pc[n,i]=Select[pc[n-1,i],Min[DegreeSequence[#]]≥n&]

Planar Connected with minimum valency >= 2

Length/@Table[pc[2,i],{i,7}]//Timing

Show[GraphicsArray[{
sg/@Complement[p[2,6],pc[2,6]],
sg/@Complement[p[2,7],pc[2,7]]
}]]

Show[GraphicsArray[{
sg/@pc[2,3],
sg/@pc[2,4],
sg/@Take[pc[2,5],5],
sg/@Take[pc[2,5],-5]
},GraphicsSpacing->{.5,.4}]]

Planar Connected with minimum valency >= 3

Length/@Table[pc[3,i],{i,7}]//Timing

Planar Connected with minimum valency >= 4

Length/@Table[pc[4,i],{i,7}]//Timing