Critical Nonplanar Graph

Author

Eric W. Weisstein
March 30, 2009

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/CriticalNonplanarGraph.nb.

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

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

Table

l=GraphData["CriticalNonplanar"];

TableForm[GraphData[#,{"V","#"}]&/@DeleteCas[GraphData["CriticalNonplanar"]//Sort,TableDepth->2]

Enumeration

(g1=Select[GraphData["Nonplanar",1],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g2=Select[GraphData["Nonplanar",2],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g=Select[GraphData["Nonplanar",3],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g4=Select[GraphData["Nonplanar",4],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g5=Select[GraphData["Nonplanar",5],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g6=Select[GraphData["Nonplanar",6],CriticalNonplanarQ[Graph[#],False]&])//Timing

(g7=Select[GraphData["Nonplanar",7],CriticalNonplanarQ[Graph[#],False]&])//Timing

Length/@{g5,g6,g7}

Length[gs8=GetGraphData[8]]//Timing

Length[g8n=Select[gs8,!MemberQ[GetGraphData[#,"Classes"],"Planar"]&]]//Timing

(g8=Select[g8n,CriticalNonplanarQ[GetGraph[#],False]&])//Timing

Length[g8]

Length[g9p=FromAdjacencyMatrix/@Import["/Volumes/Users/eww/Mathematica/Paclets/GraphData/Collections/McKay/planar_conn.9.g6","AdjacencyMatrix"]]//Timing

Length[g9=FromAdjacencyMatrix/@Import["/Volumes/Users/eww/Mathematica/Paclets/GraphData/Collections/McKay/graph9c.g6","AdjacencyMatrix"]]//Timing

cfs=CanonicalForm/@g9p;

Length[g9n=Select[g9,!MemberQ[cfs,CanonicalForm[#]]&]]

(g9nc=Select[g9n,CriticalNonplanarQ[#,False]&])//Length//Timing

Figure

garray=Flatten[Partition[#,5,5,{1,1},{}]&/@{g5,g6},1]

GraphicsGrid[Map[Show[GraphPlot[Graph[#],Method->None,BaseStyle->Italic],PlotLabel->TextCell[GraphData[#,"Name"],PageWidth->80,TextAlignment->Center]]&,garray,{2}],ImageSize->400,Spacings->{-20,20}]