I Graph

Author

Eric W. Weisstein
November 15, 2023

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

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

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

Table

Initial Pass

Flatten[With[{m=6},Table[{n,j,k},{n,3,m},{j,n-1},{k,n-1}]],2]

i=With[{m=20},Select[Flatten[Table[{n,j,k},{n,3,m},{j,n-1},{k,j/2}],2],#[[2]]!=#[[1]]/2&]];

(l={#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[{RecognizeGraph[IGraph@@#],#}&/@i,First],First])//Column

Fillins

i=With[{m=20},Select[Flatten[Table[{n,j,k},{n,3,m},{j,n-1},{k,j/2}],2],#[[2]]!=#[[1]]/2&]];

(l={#[[1,1]],#[[All,2]]}&/@SplitBy[SortBy[{RecognizeGraph[IGraph@@#],#}&/@i,First],First])//Column

Select[DeleteCases[l,{{},_}],!GraphData[#[[1]],"IGraph"]&]

Figure

gs=SortBy[{#[[1]],#[[2,1]]}&/@DeleteCases[l,{{}|{"Prism",_}|{"GeneralizedPetersen",{Except[7],_}},_}],GraphData[#[[1]],"V"]&]

GraphicsGrid[Partition[Show[GraphData[#[[1]],"Image"],PlotLabel->TextCell[Column[{If[StringMatchQ[n=GraphData[#[[1]],"Name"],"*I-graph*"],"",n],Row[{"I","(",Sequence@@Riffle[#[[2]],", "],")"}]},Center],PageWidth->120,TextAlignment->Center]]&/@gs,4,4,{1,1},{}],Spacings->{-70,20},BaseStyle->Italic,ImageSize->500]

Special cases

parms=Sort[Select[Flatten[Table[{n,j,k},{n,31},{j,n-1},{k,n-1}],2],2#[[2]]≠#[[1]]&&2#[[3]]≠#[[1]]&]];

MinimalIGraphIndices[n_,j_,k_]:=Sort[{{n,j,k},{n,j,n-k},{n,n-j,k},{n,n-j,n-k}}][[1]]

IGraphIndices[l_]:=Union[MinimalIGraphIndices@@@l]
SymmetricIGraphIndices[l_]:=Union[Sort[{{#1,#2,#3},{#1,#3,#2}}][[1]]&@@@l]

rawdata={#,RecognizeGraph[IGraph@@#]}&/@IGraphIndices[parms];//Timing

In GraphData

TextGrid[SortBy[{#[[All,1]],#[[1,2]]}&/@SplitBy[SortBy[DeleteCases[rawdata,{_,{}}],Last],Last],#[[1,1]]&],Dividers->All]

TextGrid[data=SortBy[{#[[All,1]],#[[1,2]]}&/@SplitBy[SortBy[DeleteCases[rawdata,{_,{}}],Last],Last],Last],Dividers->All]

New

Column[new=SortBy[SplitBy[Sort[{Hash[CanonicalForm[IGraph@@#]],#}&/@Cases[rawdata,{i_,{}}:>i]],First][[All,All,2]],First]]

I:

new[[All,1]]

GeneralizedPetersen:

Cases[%,{_,1,_}]

Missing GP standard names

new=DeleteCases[Cases[data,{i_,gp:{"GeneralizedPetersen",_}}:>{
gp,
Cases[GraphData[gp,"StandardNames"],{"GeneralizedPetersen",_}],
Cases[i,{n_,1,k_}:>{"GeneralizedPetersen",{n,k}}]
}],{_,x_,x_}]

l={#,{0,Union[GraphData[#,"AlternateStandardNames"],Complement[#3,#2]]}}&@@@new

PropertyReplace[l,"AlternateStandardNames",{"11.3","11.4"}]

RenameGraphFiles[]

Unit distance embedding

Zitnik et al.  2012. ALL GENERALIZED PETERSEN GRAPHS ARE UNIT-DISTANCE GRAPHS.

Solve[(R^2)+(r^2)-2R r Cos[ϕ]==1,ϕ]

FullSimplify[ArcCos[((-1+(r^2)+(R^2))/(2 r R))]/.{R->1/(2Sin[j Pi/n]),r->1/(2Sin[k Pi/n])},(k|m|n)∈Integers]

IGraphUnitDistance[n_,j_,k_,op_:Identity]:=Module[{R=1/(2Sin[j Pi/n]),r=1/(2Sin[k Pi/n]),inner,outer,phi},
phi=ArcCos[RootReduce[(1/2) (-4+((Csc[((j π)/n)])^2)+((Csc[((k π)/n)])^2)) Sin[((j π)/n)] Sin[((k π)/n)]]];
inner=CirclePoints[{r,phi},n];
outer=CirclePoints[{R,0},n];
System`Graph[Range[2n],EdgeList[IGraph[n,j,k]],VertexCoordinates->op[Join[outer,inner]]]
]

Embeddings

<<MathWorld`Graphs`

"NetGraph" (not I-graph; j,k==n)

GetGraphData["NetGraph","File"]

is=Cases[data2,{x_,gn="NetGraph"}:>x][[1]]

GetGraphData[gn,"File"]

GraphicsGrid[Partition[g=IGraph@@@is,UpTo[4]]]//StyleGraphs

GraphicsGrid[Partition[gu=IGraphUnitDistance@@@is,UpTo[4]]]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[g[[3]],GraphData[gn]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,{{"IGraph","MinimalCrossing","MinimalRectilinearCrossing","Planar","Primary"},{"IGraph"}}}}};

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"Sunlet", 4}  (not I-graph; j,k==n)

is=Cases[data2,{x_,gn={"Sunlet",4}}:>x][[1]]

GraphData[{"Sunlet",4},"IGraph"]

GraphicsGrid[Partition[IGraph@@@is,UpTo[5]]]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@#,GraphData[gn]]&/@is[[{4,5}]]]}}}//FullSimplify

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{2}]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {3, 1, 1}} == {"Prism", 3}

Names

GraphData[{"IGraph",{3,1,1}},"StandardName"]

GraphData[{"IGraph",{3,1,1}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn={"Prism",3}}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

Add

l={{gn,{0,Join[{Union[{"IGraph"},First[e=GraphData[gn,"EmbeddingClasses"]]]},Rest[e]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {4, 1, 1}} == "CubicalGraph"

Names

GraphData[{"IGraph",{4,1,1}},"StandardName"]

GraphData[{"IGraph",{4,1,1}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="CubicalGraph"}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

Add

l={{gn,{0,Join[{Union[{"IGraph"},First[e=GraphData[gn,"EmbeddingClasses"]]]},Rest[e]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {5, 1, 1}} == {"Prism", 5}

Names

GraphData[{"IGraph",{5,1,1}},"StandardName"]

GraphData[{"IGraph",{5,1,1}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn={"Prism",5}}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add EmbeddingClass

l={{gn,{0,Join[{Union[{"IGraph"},First[e=GraphData[gn,"EmbeddingClasses"]]]},Rest[e]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

Add

l={{gn,{0,ReplacePart[GraphData[gn,"Embeddings"],7->ToCommonEdges[IGraph@@is[[3]],GraphData[gn]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"IGraph"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {5, 1, 2}} == "PetersenGraph"

Names

GraphData[{"IGraph",{5,1,2}},"StandardName"]

GraphData[{"IGraph",{5,1,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="PetersenGraph"}:>x][[1]]

GraphicsGrid[Partition[IGraph@@@is,UpTo[4]]]//StyleGraphs

IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData["PetersenGraph","Graph","IGraph"]//StyleGraphs

GraphData["PetersenGraph","Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData["PetersenGraph","Graph","All"]//StyleGraphs,UpTo[5]]]

Add

l={{gn,{0,ReplacePart[GraphData[gn,"Embeddings"],11->ToCommonEdges[IGraph@@is[[1]],GraphData[gn]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"IGraph"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {6, 1, 2}} == "DuererGraph"

Names

GraphData[{"IGraph",{6,1,2}},"StandardName"]

GraphData[{"IGraph",{6,1,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="DuererGraph"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,ReplacePart[GraphData[gn,"Embeddings"],ToCommonEdges[gu[[1]],GraphData[gn]],4]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,{{"GeneralizedPetersen","IGraph","Primary"},{"MinimalCrossing","MinimalRectilinearCrossing","Planar"},{"IGraph"},{"Integral","MinimalIntegral","UnitDistance"},{},{},{"MinimalCrossing","MinimalRectilinearCrossing","Planar"}}}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {6, 2, 2}} == "2Y3"

Names

GraphData[{"IGraph",{6,2,2}},"StandardName"]

GraphData[{"IGraph",{6,2,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="2Y3"}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData["2Y3","Graph","All"]//StyleGraphs

GraphData["2Y3","Graph","IGraph"]//StyleGraphs

GraphData["2Y3","Graph","UnitDistance"]

Add

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@is[[1]],GraphData[gn]]]}}}

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"IGraph"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {7, 1, 2}} == {"GeneralizedPetersen", {7, 2}}

Names

GraphData[{"IGraph",{7,1,2}},"StandardName"]

GraphData[{"IGraph",{7,1,2}},"StandardNames"]

IGraph

is=IGraphIndices[Cases[data,{x_,gn={"GeneralizedPetersen",{7,2}}}:>x][[1]]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"]//StyleGraphs,UpTo[6]],ImageSize->600]

UnitDistanceGraphQ/@GraphData[gn,"Graph","UnitDistance"]

Add

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@{7,2,3},GraphData[gn]]]}}}

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"IGraph"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {8, 1, 3}} == "MoebiusKantorGraph"

Names

GraphData[{"IGraph",{8,1,3}},"StandardName"]

GraphData[{"IGraph",{8,1,3}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="MoebiusKantorGraph"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

Add

l={{gn,{0,Insert[GraphData[gn,"Embeddings"],ToCommonEdges[g[[1]],GraphData[gn]],4]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Insert[GraphData[gn,"EmbeddingClasses"],{"IGraph"},4]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {8, 2, 2}} == "2Q3"

Names

GraphData[{"IGraph",{8,2,2}},"StandardName"]

GraphData[{"IGraph",{8,2,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="2Q3"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

{"IGraph", {9, 3, 3}} == "3Y3"

Names

GraphData[{"IGraph",{9,3,3}},"StandardName"]

GraphData[{"IGraph",{9,3,3}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="3Y3"}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@is[[1]],GraphData[gn]]]}}}

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"IGraph"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {10, 1, 2}} == "DodecahedralGraph"

Names

GraphData[{"IGraph",{10,1,2}},"StandardName"]

GraphData[{"IGraph",{10,1,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="DodecahedralGraph"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[#,GraphData[gn]]&/@Join[g[[{1,5,7}]],gu[[{5}]]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],{{"IGraph"},{"IGraph"},{"IGraph"},{"Integral","MinimalIntegral","UnitDistance"}}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {10, 1, 3}} == "DesarguesGraph"

Names

GraphData[{"IGraph",{10,1,3}},"StandardName"]

GraphData[{"IGraph",{10,1,3}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="DesarguesGraph"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"],UpTo[4]]]//StyleGraphs

Add

l={{gn,{0,Insert[GraphData[gn,"Embeddings"],ToCommonEdges[g[[1]],GraphData[gn]],6]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Insert[GraphData[gn,"EmbeddingClasses"],{"IGraph"},6]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

GraphData[gn,"AlternateStandardNames"]

is

l={{gn,{0,{{"IGraph",{10,2,4}},{"IGraph",{10,4,2}},{"NoncayleyTransitive",{20,3}},"P+P","PP"}}}};

PropertyReplace[l,"AlternateStandardNames","11.3"]

RenameGraphFiles[]

{"IGraph", {12, 1, 5}} == "NauruGraph"

Names

GraphData[{"IGraph",{12,1,5}},"StandardName"]

GraphData[{"IGraph",{12,1,5}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="NauruGraph"}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData["NauruGraph","Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData["NauruGraph","Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"]//StyleGraphs,UpTo[5]],ImageSize->600]

Left one from Zitnik et al. 2012

Add

l={{gn,{0,Insert[GraphData[gn,"Embeddings"],ToCommonEdges[g,GraphData[gn]],3]}}}

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Insert[GraphData[gn,"EmbeddingClasses"],{"IGraph"},3]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {10, 2, 2}} == "2Y5"

Names

GraphData[{"IGraph",{10,2,2}},"StandardName"]

GraphData[{"IGraph",{10,2,2}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="2Y5"}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@#,GraphData[gn]]&/@is[[{1,3}]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{2}]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"IGraph", {10, 2, 4}} == "2P"

Names

GraphData[{"IGraph",{10,2,4}},"StandardName"]

GraphData[{"IGraph",{10,2,4}},"StandardNames"]

IGraph

is=Cases[data,{x_,gn="2P"}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,Append[GraphData[gn,"Embeddings"],ToCommonEdges[gu[[1]],GraphData[gn]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

GraphData["GolombGraph","EmbeddingClasses"]

l={{gn,{0,Append[GraphData[gn,"EmbeddingClasses"],{"Integral","MinimalIntegral","UnitDistance"}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

GraphData[gn,"AlternateStandardNames"]

is

l={{gn,{0,{{"IGraph",{10,2,4}},{"IGraph",{10,4,2}},{"NoncayleyTransitive",{20,3}},"P+P","PP"}}}};

PropertyReplace[l,"AlternateStandardNames","11.3"]

RenameGraphFiles[]

{"GeneralizedPetersen", {8, 2}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{8,2}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn,"Graph","All"]//StyleGraphs,UpTo[6]],ImageSize->600]

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[#,GraphData[gn]]&/@Join[g[[{1,4,7}]],gu[[{4}]]]]}}}//FullSimplify

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],{{"IGraph"},{"IGraph"},{"IGraph"},{"Integral","MinimalIntegral","UnitDistance"}}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"GeneralizedPetersen", {9, 2}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{9,2}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph"]

GraphicsGrid[Partition[GraphData[gn,"Graph","All"]//StyleGraphs,UpTo[6]],ImageSize->600]

Add

is[[{1,2,5,6,9,10}]]

l={{gn,{0,Join[{ToCommonEdges[g[[5]],GraphData[gn]]},Rest@GraphData[gn,"Embeddings"],ToCommonEdges[#,GraphData[gn]]&/@Join[g[[{1,2,6,9,10}]],gu[[{6}]]]]}}}//FullSimplify

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{5}],{{"Integral","MinimalIntegral","UnitDistance"}}]}}}

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,{{"GeneralizedPetersen","IGraph","Primary"},{"Circular","LCF"},{"Integral","MinimalIntegral","UnitDistance"},{"Integral","MinimalIntegral","UnitDistance"},{"IGraph"},{"IGraph"},{"IGraph"},{"IGraph"},{"IGraph"},{"Degenerate","Integral","MinimalIntegral","UnitDistance"}}}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"GeneralizedPetersen", {9, 3}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{9,3}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

Add

l={{gn,{0,Join[Rest@GraphData[gn,"Embeddings"],ToCommonEdges[#,GraphData[gn]]&/@Delete[g,{}]]}}}//FullSimplify

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{5}],{{"Integral","MinimalIntegral","UnitDistance"}}]}}}

GraphData[gn,"EmbeddingClasses"]

l={{gn,{0,{{"GeneralizedPetersen","IGraph","Primary"},{"Circular","LCF"},{"Integral","MinimalIntegral","UnitDistance"},{"Integral","MinimalIntegral","UnitDistance"},{"IGraph"},{"IGraph"},{"IGraph"},{"IGraph"},{"IGraph"},{"Degenerate","Integral","MinimalIntegral","UnitDistance"}}}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"GeneralizedPetersen", {10, 4}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{10,4}}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphicsGrid[Partition[GraphData[gn={"GeneralizedPetersen",{10,4}},"Graph","All"]//StyleGraphs,UpTo[4]]]

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[#,GraphData[gn]]&/@Append[ig[[{2,3,5}]],IGraphUnitDistance[10,2,3]]]}}}//FullSimplify//ToRadicals

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{3}],{{"Integral","MinimalIntegral","UnitDistance"}}]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"GeneralizedPetersen", {11, 2}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{11,2}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

{"GeneralizedPetersen", {12,2}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{12,2}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

{"GeneralizedPetersen", {31, 11}}

is=Cases[data,{x_,gn={"GeneralizedPetersen",{31,11}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

{"IGraph", {12, 2, 3}}

Names

GraphData[{"IGraph",{12,2,3}},"StandardName"]

GraphData[{"IGraph",{12,2,3}},"StandardNames"]

Primary

GraphData[{"IGraph",{12,2,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IGraph",{12,2,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"IGraph",{12,2,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"IGraph",{12,2,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"IGraph",{12,2,3}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"IGraph",{12,2,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IGraph",{12,2,3}},"Graph","Degenerate"]

Perspective

GraphData[{"IGraph",{12,2,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IGraph",{12,2,3}},"Polyhedron"]

Bilateral

GraphData[{"IGraph",{12,2,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IGraph",{12,2,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IGraph",{12,2,3}},"Planar"]

GraphData[{"IGraph",{12,2,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{12,2,3}},{"RCN","CN"}]

GraphData[{"IGraph",{12,2,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"IGraph",{12,2,3}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IGraph",{12,2,3}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IGraph",{12,2,3}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IGraph",{12,2,3}}],"CrossingNumber"->cn,RandomSeed->n]],{n,500}],Max[OuterFace[#]]<=GraphData[{"IGraph",{12,2,3}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IGraph",{12,2,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

IGraph

GraphData[{"IGraph",{12,2,3}},"Graph","IGraph"]//StyleGraphs

gs=IGraph@@@GraphData[{"IGraph",{12,2,3}},"StandardNames"][[All,2]]

Circulant

GraphData[{"IGraph",{12,2,3}},"Circulant"]

GraphData[{"IGraph",{12,2,3}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"IGraph",{12,2,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"IGraph",{12,2,3}},"Line"]

LineGraphQ[GraphData[{"IGraph",{12,2,3}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IGraph",{12,2,3}}&]

RootGraph[GraphData[{"IGraph",{12,2,3}}]]

Halin

GraphData[{"IGraph",{12,2,3}},"Halin"]

GraphData[{"IGraph",{12,2,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IGraph",{12,2,3}},"Rigid"]

GraphData[{"IGraph",{12,2,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IGraph",{12,2,3}},"Flexible"]

GraphData[{"IGraph",{12,2,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IGraph",{12,2,3}},"LCF"]

GraphData[{"IGraph",{12,2,3}},"HamiltonianCycleCount"]

GraphData[{"IGraph",{12,2,3}},"LCFSignature"]

GraphData[{"IGraph",{12,2,3}},"LCFNotations"]

GraphData[{"IGraph",{12,2,3}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"IGraph",{12,2,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IGraph",{12,2,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"IGraph",{12,2,3}}],All])[[All,2]]]//Timing

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"IGraph",{12,2,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IGraph",{12,2,3}}],Debug->True]//Timing

GraphData[{"IGraph",{12,2,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IGraph",{12,2,3}},"VertexList"],GraphData[{"IGraph",{12,2,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"IGraph",{12,2,3}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"IGraph",{12,2,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"IGraph",{12,2,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"IGraph",{12,2,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"IGraph",{12,2,3}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

gs={,,};

Matchstick

GraphData[{"IGraph",{12,2,3}},"Matchstick"]

GraphData[{"IGraph",{12,2,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IGraph",{12,2,3}},"Edges"]]

3D All

GraphData[{"IGraph",{12,2,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IGraph",{12,2,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IGraph",{12,2,3}},"Polyhedral"]

GraphData[{"IGraph",{12,2,3}},"Graph",{"3D","Polyhedron"}]

{"IGraph", {12, 3, 4}}

Names

GraphData[{"IGraph",{12,3,4}},"StandardName"]

GraphData[{"IGraph",{12,3,4}},"StandardNames"]

Primary

GraphData[{"IGraph",{12,3,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IGraph",{12,3,4}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"IGraph",{12,3,4}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"IGraph",{12,3,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"IGraph",{12,3,4}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"IGraph",{12,3,4}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IGraph",{12,3,4}},"Graph","Degenerate"]

Perspective

GraphData[{"IGraph",{12,3,4}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IGraph",{12,3,4}},"Polyhedron"]

Bilateral

GraphData[{"IGraph",{12,3,4}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IGraph",{12,3,4}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IGraph",{12,3,4}},"Planar"]

GraphData[{"IGraph",{12,3,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{12,3,4}},{"RCN","CN"}]

GraphData[{"IGraph",{12,3,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"IGraph",{12,3,4}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IGraph",{12,3,4}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IGraph",{12,3,4}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IGraph",{12,3,4}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"IGraph",{12,3,4}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IGraph",{12,3,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,4Pi/7]

v={#/9,#2/7}&@@@{{0,0},{3,0},{6,0},{9,0},{3,1},{6,1},{3,2},{6,2},{3,3},{4,3},{5,3},{6,3},{1,4},{2,4},{3,4},{6,4},{7,4},{8,4},{3,5},{6,5},{3,6},{6,6},{0,7},{9,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,24,21,19,15,9,7,5,2],e[3,6,8,12,16,20,22,23,1,13,23],e[4,18,24],e[13,14,15],e[16,17,18],{5,6},{14,21},{22,17},{9,10},{11,12},e[7,10,20],e[8,11,19]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

GraphPlot@

v={#/5,#2/9}&@@@{{0,0},{5,0},{2,1},{3,1},{2,2},{3,2},{1,3},{2,3},{3,3},{4,3},{2,4},{3,4},{2,5},{3,5},{1,6},{2,6},{3,6},{4,6},{2,7},{3,7},{2,8},{3,8},{0,9},{5,9}};
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,18,20,17,14,12,9,6,10,24,23,7,5,8,11,13,16,19,15,1,3,4,2],e[23,21,22,24],{15,16},{17,18},{7,8},{9,10},{13,14},{11,12},{19,21},{20,22},{3,5},{4,6}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@RotateGraph[,Pi/2]

v={{0,0},{7,0},{1,1},{2,1},{3,1},{4,1},{5,1},{6,1},{1,2},{3,2},{4,2},{6,2},{3,3},{4,3},{2,4},{3,4},{4,4},{5,4},{3,5},{4,5},{1,6},{6,6},{0,7},{7,7}}/7;
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,24,23,1,3,4,5,6,7,8,2],e[3,9,21,22,12,8],e[21,19,20,22],e[23,15,16],e[17,18,24],{4,9},{7,12},e[5,10,13,16,19],e[6,11,14,17,20],{10,11},{13,15},{14,18}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

GraphPlot@

v={#/5,#2/7}&@@@Join[{{0,0},{5,0},{1,1},{4,1}},Sequence@@Table[{i,j},{i,4},{j,2,5}],{{1,6},{4,6},{0,7},{5,7}}];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[1,2,24,23,1,3,5,6,7,8,21,23],e[2,4,17,18,19,20,22,24],e[3,9,14,15,12,21],e[22,16,11,10,13,4],{8,12},{16,20},{7,11},{15,19},{6,10},{14,18},{5,9},{13,17}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

gs=UnlabelGraph/@{,,,}

IGraph

GraphData[{"IGraph",{12,3,4}},"Graph","IGraph"]//StyleGraphs

GraphData[{"IGraph",{12,3,4}},"StandardNames"][[All,2]]

IGraph@@@%

gs=%[[{1,2}]]

Circulant

GraphData[{"IGraph",{12,3,4}},"Circulant"]

GraphData[{"IGraph",{12,3,4}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"IGraph",{12,3,4}},"ComplementGraph","Name"]

Line graph

GraphData[{"IGraph",{12,3,4}},"Line"]

LineGraphQ[GraphData[{"IGraph",{12,3,4}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IGraph",{12,3,4}}&]

RootGraph[GraphData[{"IGraph",{12,3,4}}]]

Halin

GraphData[{"IGraph",{12,3,4}},"Halin"]

GraphData[{"IGraph",{12,3,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IGraph",{12,3,4}},"Rigid"]

GraphData[{"IGraph",{12,3,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IGraph",{12,3,4}},"Flexible"]

GraphData[{"IGraph",{12,3,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IGraph",{12,3,4}},"LCF"]

GraphData[{"IGraph",{12,3,4}},"HamiltonianCycleCount"]

GraphData[{"IGraph",{12,3,4}},"LCFSignature"]

GraphData[{"IGraph",{12,3,4}},"LCFNotations"]

GraphData[{"IGraph",{12,3,4}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"IGraph",{12,3,4}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IGraph",{12,3,4}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"IGraph",{12,3,4}}],All])[[All,2]]]//Timing

lcf

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"IGraph",{12,3,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IGraph",{12,3,4}}],Debug->True]//Timing

GraphData[{"IGraph",{12,3,4}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IGraph",{12,3,4}},"VertexList"],GraphData[{"IGraph",{12,3,4}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"IGraph",{12,3,4}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs=LabelGraph/@{RotateGraph[,{4,1}],RotateGraph[,{16,19}]}

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"IGraph",{12,3,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"IGraph",{12,3,4}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"IGraph",{12,3,4}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"IGraph",{12,3,4}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

gs={,,,};

Matchstick

GraphData[{"IGraph",{12,3,4}},"Matchstick"]

GraphData[{"IGraph",{12,3,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IGraph",{12,3,4}},"Edges"]]

3D All

GraphData[{"IGraph",{12,3,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IGraph",{12,3,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IGraph",{12,3,4}},"Polyhedral"]

GraphData[{"IGraph",{12,3,4}},"Graph",{"3D","Polyhedron"}]

{"IGraph", {15, 3, 5}}

GraphData[{"IGraph",{15,3,5}},"StandardName"]

Default

GraphData[{"IGraph",{15,3,5}}]//StyleGraphs

All

GraphData[{"IGraph",{15,3,5}},"Graph","All"]//StyleGraphs

IGraph

GraphData[{"IGraph",{15,3,5}},"Graph","IGraph"]//StyleGraphs

LCF

GraphData[{"IGraph",{15,3,5}},"LCFSignature"]

GraphData[{"IGraph",{15,3,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

UnitDistanceGraphQ[GraphData[{"IGraph",{15,3,5}}],Debug->True]

GraphData[{"IGraph",{15,3,5}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"IGraph",{15,3,5}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

l=FindSubgraphIsomorphism[GraphData[{"IGraph",{15,3,5}}],"Results"->All]//Timing

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"IGraph",{15,3,5}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{15,3,5}},{"RCN","CN"}]

GraphData[{"IGraph",{15,3,5}},"Graph","MinimalCrossing"]//StyleGraphs

3D

Graph3D[GraphData[{"IGraph",{15,3,5}},"Edges"]]

Default embedding

GraphPlot@RotateGraph[Graph[GraphData[{"IGraph",{15,3,5}},"Edges"]],Pi/2]

GraphicsToGraph@

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistance construction

is=Cases[data,{x_,gn={"IGraph",{15,3,5}}}:>x][[1]]

g=IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

MinimalCrossing Construction

GraphData[{"IGraph",{15,3,5}},"V"]

GraphPlot@RotateGraph[Graph@MinimalCrossingGraph[GraphData[{"IGraph",{15,3,5}}],"CrossingNumber"->4],{24,27}]

v={{2,0},{9,0},{0,0},{2,1},{6,1},{9,1},{11,0},{1,2},{4,2},{7,2},{10,2},{2,3},{3,3},{4,3},{5,3},{6,3},{2,4},{6,4},{9,4},{4,5},{7,5},{8,5},{9,5},{0,7},{2,6},{6,6},{9,6},{11,7},{2,7},{9,7}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,7,28,30,29,24,3,1,4,12,17,25,29],e[30,27,23,19,6,2],e[4,5,6],e[25,26,27],e[3,8,24],e[7,11,28],e[8,9,10,11],e[12,13,14],e[15,16],{17,13},e[9,14,20,21,22,23],e[5,16,18,26],{22,19},{10,21},e[20,15,18]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

{"IGraph", {18, 2, 3}}

Names

GraphData[{"IGraph",{18,2,3}},"StandardName"]

GraphData[{"IGraph",{18,2,3}},"StandardNames"]

Primary

GraphData[{"IGraph",{18,2,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IGraph",{18,2,3}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"IGraph",{18,2,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"IGraph",{18,2,3}},"EdgeList"]]

Default embedding

g=Graph[GraphData[{"IGraph",{18,2,3}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"IGraph",{18,2,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IGraph",{18,2,3}},"Graph","Degenerate"]

Perspective

GraphData[{"IGraph",{18,2,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IGraph",{18,2,3}},"Polyhedron"]

Bilateral

GraphData[{"IGraph",{18,2,3}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IGraph",{18,2,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IGraph",{18,2,3}},"Planar"]

GraphData[{"IGraph",{18,2,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{18,2,3}},{"RCN","CN"}]

GraphData[{"IGraph",{18,2,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"IGraph",{18,2,3}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IGraph",{18,2,3}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IGraph",{18,2,3}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IGraph",{18,2,3}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"IGraph",{18,2,3}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IGraph",{18,2,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

IGraph

GraphData[{"IGraph",{18,2,3}},"Graph","IGraph"]//StyleGraphs

GraphData[{"IGraph",{18,2,3}},"StandardNames"][[All,2]]

gs=IGraph@@@%

Circulant

GraphData[{"IGraph",{18,2,3}},"Circulant"]

GraphData[{"IGraph",{18,2,3}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"IGraph",{18,2,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"IGraph",{18,2,3}},"Line"]

LineGraphQ[GraphData[{"IGraph",{18,2,3}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IGraph",{18,2,3}}&]

RootGraph[GraphData[{"IGraph",{18,2,3}}]]

Halin

GraphData[{"IGraph",{18,2,3}},"Halin"]

GraphData[{"IGraph",{18,2,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IGraph",{18,2,3}},"Rigid"]

GraphData[{"IGraph",{18,2,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IGraph",{18,2,3}},"Flexible"]

GraphData[{"IGraph",{18,2,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IGraph",{18,2,3}},"LCF"]

GraphData[{"IGraph",{18,2,3}},"HamiltonianCycleCount"]

GraphData[{"IGraph",{18,2,3}},"LCFSignature"]

GraphData[{"IGraph",{18,2,3}},"LCFNotations"]

GraphData[{"IGraph",{18,2,3}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"IGraph",{18,2,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IGraph",{18,2,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"IGraph",{18,2,3}}],All])[[All,2]]]//Timing

lcf

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"IGraph",{18,2,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IGraph",{18,2,3}}],Debug->True]//Timing

GraphData[{"IGraph",{18,2,3}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IGraph",{18,2,3}},"VertexList"],GraphData[{"IGraph",{18,2,3}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"IGraph",{18,2,3}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,,};

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"IGraph",{18,2,3}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"IGraph",{18,2,3}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"IGraph",{18,2,3}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"IGraph",{18,2,3}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"IGraph",{18,2,3}},"Matchstick"]

GraphData[{"IGraph",{18,2,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IGraph",{18,2,3}},"Edges"]]

3D All

GraphData[{"IGraph",{18,2,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IGraph",{18,2,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IGraph",{18,2,3}},"Polyhedral"]

GraphData[{"IGraph",{18,2,3}},"Graph",{"3D","Polyhedron"}]

{"IGraph", {20, 2, 5}}

Names

GraphData[{"IGraph",{20,2,5}},"StandardName"]

GraphData[{"IGraph",{20,2,5}},"StandardNames"]

Primary

GraphData[{"IGraph",{20,2,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IGraph",{20,2,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"IGraph",{20,2,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"IGraph",{20,2,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"IGraph",{20,2,5}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"IGraph",{20,2,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IGraph",{20,2,5}},"Graph","Degenerate"]

Perspective

GraphData[{"IGraph",{20,2,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IGraph",{20,2,5}},"Polyhedron"]

Bilateral

GraphData[{"IGraph",{20,2,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IGraph",{20,2,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IGraph",{20,2,5}},"Planar"]

GraphData[{"IGraph",{20,2,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{20,2,5}},{"RCN","CN"}]

GraphData[{"IGraph",{20,2,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"IGraph",{20,2,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IGraph",{20,2,5}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IGraph",{20,2,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IGraph",{20,2,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"IGraph",{20,2,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IGraph",{20,2,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

IGraph

GraphData[{"IGraph",{20,2,5}},"Graph","IGraph"]//StyleGraphs

GraphData[{"IGraph",{20,2,5}},"StandardNames"][[All,2]]

gs=IGraph@@@%

Circulant

GraphData[{"IGraph",{20,2,5}},"Circulant"]

GraphData[{"IGraph",{20,2,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"IGraph",{20,2,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"IGraph",{20,2,5}},"Line"]

LineGraphQ[GraphData[{"IGraph",{20,2,5}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IGraph",{20,2,5}}&]

RootGraph[GraphData[{"IGraph",{20,2,5}}]]

Halin

GraphData[{"IGraph",{20,2,5}},"Halin"]

GraphData[{"IGraph",{20,2,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IGraph",{20,2,5}},"Rigid"]

GraphData[{"IGraph",{20,2,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IGraph",{20,2,5}},"Flexible"]

GraphData[{"IGraph",{20,2,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IGraph",{20,2,5}},"LCF"]

GraphData[{"IGraph",{20,2,5}},"HamiltonianCycleCount"]

GraphData[{"IGraph",{20,2,5}},"LCFSignature"]

GraphData[{"IGraph",{20,2,5}},"LCFNotations"]

GraphData[{"IGraph",{20,2,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"IGraph",{20,2,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IGraph",{20,2,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"IGraph",{20,2,5}}],All])[[All,2]]]//Timing

lcf

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"IGraph",{20,2,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IGraph",{20,2,5}}],Debug->True]//Timing

GraphData[{"IGraph",{20,2,5}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IGraph",{20,2,5}},"VertexList"],GraphData[{"IGraph",{20,2,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"IGraph",{20,2,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,,};

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"IGraph",{20,2,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"IGraph",{20,2,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"IGraph",{20,2,5}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"IGraph",{20,2,5}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"IGraph",{20,2,5}},"Matchstick"]

GraphData[{"IGraph",{20,2,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IGraph",{20,2,5}},"Edges"]]

3D All

GraphData[{"IGraph",{20,2,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IGraph",{20,2,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IGraph",{20,2,5}},"Polyhedral"]

GraphData[{"IGraph",{20,2,5}},"Graph",{"3D","Polyhedron"}]

{"IGraph", {20, 4, 5}}

Names

GraphData[{"IGraph",{20,4,5}},"StandardName"]

GraphData[{"IGraph",{20,4,5}},"StandardNames"]

Primary

GraphData[{"IGraph",{20,4,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IGraph",{20,4,5}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"IGraph",{20,4,5}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"IGraph",{20,4,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"IGraph",{20,4,5}},"Edges"]

v={};
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"IGraph",{20,4,5}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IGraph",{20,4,5}},"Graph","Degenerate"]

Perspective

GraphData[{"IGraph",{20,4,5}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IGraph",{20,4,5}},"Polyhedron"]

Bilateral

GraphData[{"IGraph",{20,4,5}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IGraph",{20,4,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IGraph",{20,4,5}},"Planar"]

GraphData[{"IGraph",{20,4,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IGraph",{20,4,5}},{"RCN","CN"}]

GraphData[{"IGraph",{20,4,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"IGraph",{20,4,5}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IGraph",{20,4,5}}],TimeConstraint->10])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IGraph",{20,4,5}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

IGLayoutTutte[g,"OuterFace"->#]&/@faces

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IGraph",{20,4,5}}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"IGraph",{20,4,5}},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IGraph",{20,4,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union

GraphPlot@RotateGraph[,3Pi/8]

Mean[{v[[4]],{1/2,1/2}}]//FullSimplify

Mean[v[[{35,25}]]]

v=UnitCirclePoints[8];
v=Join[v,{{(1/2),(1/4) (2+(Sqrt[2]))},{((-1)/2),(1/4) (2+(Sqrt[2]))},{(1/2),-(1/4) (2+(Sqrt[2]))},{((-1)/2),((-1)/4) (2+(Sqrt[2]))}},Reverse/@{{(1/2),(1/4) (2+(Sqrt[2]))},{((-1)/2),(1/4) (2+(Sqrt[2]))},{(1/2),-(1/4) (2+(Sqrt[2]))},{((-1)/2),((-1)/4) (2+(Sqrt[2]))}}];
v=Join[v,Subdivide[{-1/2,1/4},{1/2,1/4},5],Subdivide[{-1/2,-1/4},{1/2,-1/4},5]];
v=Join[v,{v[[#,1]],1/2}&/@{19,20},{v[[#,1]],-1/2}&/@{19,20}];
v=Join[v,Mean[v[[#]]]&/@{{15,16},{13,14}}];
v=Join[v,{v[[#,1]],0}&/@{19,20}];
v=Join[v,{v[[#,1]],-1/8}&/@{24,25,26,27}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,7,8,1,11,28,22,9,4],e[5,10,17,23,12,8],{12,11},{10,9},e[6,15,29,30,13,3],e[7,16,31,32,14,2],e[16,33,15],e[14,34,13],e[{17,22}],e[{23,28}],{19,29},{20,30},{25,31},{26,32},e[33,35,36,34],e[24,37,18],e[27,40,21],e[37,38,39,40],{38,35},{39,36}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

IGraph

GraphData[{"IGraph",{20,4,5}},"Graph","IGraph"]//StyleGraphs

GraphData[{"IGraph",{20,4,5}},"StandardNames"][[All,2]]

IGraph@@@%

gs=%[[{1,2,3,4}]]

Circulant

GraphData[{"IGraph",{20,4,5}},"Circulant"]

GraphData[{"IGraph",{20,4,5}},"Graph","Circulant"]//StyleGraphs

Complement graph

GraphData[{"IGraph",{20,4,5}},"ComplementGraph","Name"]

Line graph

GraphData[{"IGraph",{20,4,5}},"Line"]

LineGraphQ[GraphData[{"IGraph",{20,4,5}}]]//Timing

RootGraph

Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IGraph",{20,4,5}}&]

RootGraph[GraphData[{"IGraph",{20,4,5}}]]

Halin

GraphData[{"IGraph",{20,4,5}},"Halin"]

GraphData[{"IGraph",{20,4,5}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IGraph",{20,4,5}},"Rigid"]

GraphData[{"IGraph",{20,4,5}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IGraph",{20,4,5}},"Flexible"]

GraphData[{"IGraph",{20,4,5}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IGraph",{20,4,5}},"LCF"]

GraphData[{"IGraph",{20,4,5}},"HamiltonianCycleCount"]

GraphData[{"IGraph",{20,4,5}},"LCFSignature"]

GraphData[{"IGraph",{20,4,5}},"LCFNotations"]

GraphData[{"IGraph",{20,4,5}},"Graph","LCF"]//StyleGraphs

Tally[LCFNotation[#][[2]]&/@%]

LCF compute all

Divisors[GraphData[{"IGraph",{20,4,5}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IGraph",{20,4,5}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"IGraph",{20,4,5}}],All])[[All,2]]]//Timing

lcf

LCFGraph@@@lcf//StyleGraphs

Tally[LCFNotation[#][[-1]]&/@(gs=NiceLCFGraphs[lcf,2,1])]//Timing

Length[gs]

gs

UnitDistance

GraphData[{"IGraph",{20,4,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IGraph",{20,4,5}}],Debug->True]//Timing

GraphData[{"IGraph",{20,4,5}},"Graph","UnitDistance"]//StyleGraphs

Select[%,!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&]

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IGraph",{20,4,5}},"VertexList"],GraphData[{"IGraph",{20,4,5}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine[Annotate[#,VertexCoordinates->N[GraphEmbedding[#]]],MaxIterations->500]&/@Complement@@(GraphData[{"IGraph",{20,4,5}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

gs={,};

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"IGraph",{20,4,5}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"IGraph",{20,4,5}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"IGraph",{20,4,5}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"IGraph",{20,4,5}}],TimeConstraint->300,"Results"->All]//Timing}

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Matchstick

GraphData[{"IGraph",{20,4,5}},"Matchstick"]

GraphData[{"IGraph",{20,4,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IGraph",{20,4,5}},"Edges"]]

3D All

GraphData[{"IGraph",{20,4,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IGraph",{20,4,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IGraph",{20,4,5}},"Polyhedral"]

GraphData[{"IGraph",{20,4,5}},"Graph",{"3D","Polyhedron"}]

{"Prism", 6}

is=Cases[data,{x_,gn={"Prism",6}}:>x][[1]]

IGraph@@@is//StyleGraphs

gu=IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[is]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

{"Prism", 7}

is=Cases[data,{x_,gn={"Prism",7}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

Add

l={{gn,{0,Join[GraphData[gn,"Embeddings"],ToCommonEdges[IGraph@@#,GraphData[gn]]&/@is[[{4,5}]]]}}}//FullSimplify

PropertyReplace[l,"Embeddings","11.3"]

RenameGraphFiles[]

l={{gn,{0,Join[GraphData[gn,"EmbeddingClasses"],Table[{"IGraph"},{2}]]}}}

PropertyReplace[l,"EmbeddingClasses","11.3"]

RenameGraphFiles[]

{"Prism", 8}

is=Cases[data,{x_,gn={"Prism",8}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

{"Prism", 9}

is=Cases[data,{x_,gn={"Prism",9}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

{"Prism", 10}

is=Cases[data,{x_,gn={"Prism",9}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

{"Prism", 19}

is=Cases[data,{x_,gn={"Prism",19}}:>x][[1]]

IGraph@@@is//StyleGraphs

GraphData[gn,"Graph","IGraph"]//StyleGraphs

GraphData[gn,"Graph","UnitDistance"]//StyleGraphs

GraphData[gn,"Graph","All"]//StyleGraphs

GraphData

GraphDataString

(add=Select[new,#[[1,1]]≤20&])//Column

TextGrid[rec=Map[{#,Tally[RecognizeGraph/@ConnectedGraphComponents[IGraph@@#]]}&,add[[All,1]],{1}],Dividers->All]

Function[g,Select[IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[g],(e=Sort[Chop@N[GraphEmbedding[#]]])===Union[e]&]]/@add

ne=Chop@N[e,20];

Connected:

con=Select[new[[All,1]],ConnectedQ[IGraph@@#]&]

GP:

Select[add,Intersection[#[[All,2]],{1}]=!={}&]

GraphData["IGraph*"]

GraphData[{"IGraph",{12,2,3}},"Name"]

file=OpenWrite["~/igraph.m"]

RecognizeGraph[GraphDisjointUnion@@Table[PrismGraph[6],{2}]]

Select[IGraph[Sequence@@#,GraphLayout->"UnitDistance"]&/@SymmetricIGraphIndices[g],(e=Sort[Chop@N[GraphEmbedding[#]]])===Union[e]&]

WriteString[file,GraphDataString[g=IGraph@@#[[1]],
"StandardName"->{"IGraph",#[[1]]},
"AlternateStandardNames"->Function[r,{"IGraph",#}]/@Rest[#],
"Name"->"("<>StringReplace[StringTake[ToString[#[[1]]],{2,-2}]," "->""]<>")-I graph",
"AlternateNames"->Function[r,"("<>StringReplace[StringTake[ToString[r],{2,-2}], " "->""]<>")\[Hyphen]I graph"]/@Rest[#],
"Embeddings"->Function[e,ToCommonEdges[e,g]]/@Join[
IGraph@@@#,
unit=Select[DeleteCases[Function[i,IGraph[Sequence@@i,GraphLayout->"UnitDistance"]]/@SymmetricIGraphIndices[#],$Failed],(e=Sort[Chop@N[GraphEmbedding[#]]])===Union[e]&]
],
"EmbeddingClasses"->Join[
Table[{"IGraph",If[i==1,"Primary",Nothing]},{i,Length[#]}],
Table[{"Integral","MinimalIntegral","UnitDistance"},{Length[unit]}]
],
"Information"->"IGraph",
"Classes"->{"IGraph","UnitDistance"},
"NotationRules"->{"IGraph"->#[[1]]},
TimeConstraint->10
]]&/@Take[add,1]

Close[file]