KP Graph

Author

Eric W. Weisstein
January 5, 2025

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

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

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

Source

Knuth, D.E.  The Art of Computer Programing, Vol. 4, Pre-Fascicle 7A, §7.2.2.3, p. 20, 2024.

p. 21

Properties

AutomorphismCount

DeleteCases[{#,{n,r}=GraphData[#,"NotationRules","KP"],GraphData[#,"AutomorphismCount"],Piecewise[{{1,r==1},{4,r==n==2}},2]n!}&/@GraphData["KP"],{_,_,x_,x_}]

EdgeCount

DeleteCases[{#,{n,r}=GraphData[#,"NotationRules","KP"],GraphData[#,"EdgeCount"],r Binomial[n,2]+(r-1)n}&/@GraphData["KP"],{_,_,x_,x_}]

VertexCount

DeleteCases[{#,{n,r}=GraphData[#,"NotationRules","KP"],GraphData[#,"VertexCount"],r n}&/@GraphData["KP"],{_,_,x_,x_}]

Classes that are Class

GraphClassesThatAre["KP"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["KP"])

Table

TextGrid[Table[{n,r,RecognizeGraph@KPGraph[n,r]},{n,10},{r,5}],Dividers->All]

Embeddings

<<MathWorld`Graphs`

{"KP", {3, 1}} == "TriangleGraph"

Names

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

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

{"KP", {3, 2}} == {"Prism", 3}

Names

GraphData[{"KP",{3,2}},"StandardName"]

GraphData[{"KP",{3,2}},"StandardNames"]

{"KP", {3, 3}} == {"StackedPrism", {3, 3}}

Names

GraphData[{"KP",{3,3}},"StandardName"]

GraphData[{"KP",{3,3}},"StandardNames"]

{"KP", {3, 4}} == {"StackedPrism", {3, 4}}

Names

GraphData[{"KP",{3,4}},"StandardName"]

GraphData[{"KP",{3,4}},"StandardNames"]

{"KP", {3, 5}} == {"StackedPrism", {3, 5}}

Names

GraphData[{"KP",{3,5}},"StandardName"]

GraphData[{"KP",{3,5}},"StandardNames"]

{"KP", {3, 6}} == {"StackedPrism", {3, 6}}

Names

GraphData[{"KP",{3,6}},"StandardName"]

GraphData[{"KP",{3,6}},"StandardNames"]

{"KP", {3, 7}} == {"StackedPrism", {3, 7}}

Names

GraphData[{"KP",{3,7}},"StandardName"]

GraphData[{"KP",{3,7}},"StandardNames"]

{"KP", {3, 8}} == {"StackedPrism", {3, 8}}

Names

GraphData[{"KP",{3,8}},"StandardName"]

GraphData[{"KP",{3,8}},"StandardNames"]

{"KP", {3, 9}} == {"StackedPrism", {3, 9}}

Names

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

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

{"KP", {3, 10}} == {"StackedPrism", {3, 10}}

Names

GraphData[{"KP",{3,10}},"StandardName"]

GraphData[{"KP",{3,10}},"StandardNames"]

{"KP", {4, 3}}

Names

GraphData[{"KP",{4,3}},"StandardName"]

GraphData[{"KP",{4,3}},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KP",{4,3}}]]

Default embedding

g=Graph[GraphData[{"KP",{4,3}},"VertexList"],GraphData[{"KP",{4,3}},"Edges"]]

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

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KP",{4,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KP",{4,3}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KP",{4,3}},"Hamiltonian"]

GraphData[{"KP",{4,3}},"LCF"]

GraphData[{"KP",{4,3}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KP",{4,3}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KP",{4,3}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Planar

GraphData[{"KP",{4,3}},"Planar"]

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

MinimalCrossing

GraphData[{"KP",{4,3}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"KP",{4,3}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,3}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,3}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,3}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,3}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KP",{4,3}},"V"]&]

GraphPlot@

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"KP",{4,3}}],"CrossingNumber"->cn,RandomSeed->n]],{n,5000}],Max[OuterFace[#]]<=GraphData[{"KP",{4,3}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,3}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KP",{4,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,5000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,3}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KP",{4,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KP",{4,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,3}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,3}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,3}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,3}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,3}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KP",{4,3}},"Circulant"]

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

Circulant construction

GraphData[{"KP",{4,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KP",{4,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KP",{4,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KP",{4,3}},"ComplementGraph","Name"]

Line graph

GraphData[{"KP",{4,3}},"Line"]

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

RootGraph

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

RootGraph[GraphData[{"KP",{4,3}}]]

RecognizeGraph[%]

Halin

GraphData[{"KP",{4,3}},"Halin"]

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

Rigid

GraphData[{"KP",{4,3}},"Rigid"]

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

Flexible

GraphData[{"KP",{4,3}},"Flexible"]

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

LCF

GraphData[{"KP",{4,3}},"LCF"]

GraphData[{"KP",{4,3}},"HamiltonianCycleCount"]

GraphData[{"KP",{4,3}},"LCFSignature"]

GraphData[{"KP",{4,3}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"KP",{4,3}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"KP",{4,3}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"KP",{4,3}},"Edges"]]

3D construction

v=GraphData[{"Grid",{2,2,3}},"Embeddings",{"3D","All"}][[2]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"KP",{4,3}},"Polyhedral"]

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

{"KP", {4, 4}}

Names

GraphData[{"KP",{4,4}},"StandardName"]

GraphData[{"KP",{4,4}},"StandardNames"]

Primary

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

All

GraphData[{"KP",{4,4}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KP",{4,4}}]]

Default embedding

g=Graph[GraphData[{"KP",{4,4}},"VertexList"],GraphData[{"KP",{4,4}},"Edges"]]

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

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KP",{4,4}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

GraphData[{"KP",{4,4}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KP",{4,4}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"KP",{4,4}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KP",{4,4}},"Hamiltonian"]

GraphData[{"KP",{4,4}},"LCF"]

GraphData[{"KP",{4,4}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KP",{4,4}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KP",{4,4}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

gs={,,,,,,,,,,,,,,,,,,,,,,,,,,};

Planar

GraphData[{"KP",{4,4}},"Planar"]

GraphData[{"KP",{4,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"KP",{4,4}},{"RCN","CN"}]

GraphData[{"KP",{4,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"KP",{4,4}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,4}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,4}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,4}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KP",{4,4}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"KP",{4,4}}],"CrossingNumber"->cn,RandomSeed->n]],{n,5000}],Max[OuterFace[#]]<=GraphData[{"KP",{4,4}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KP",{4,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,5000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KP",{4,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,4}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KP",{4,4}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,4}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,4}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,4}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,4}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KP",{4,4}},"Circulant"]

GraphData[{"KP",{4,4}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KP",{4,4}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KP",{4,4}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KP",{4,4}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KP",{4,4}},"ComplementGraph","Name"]

Line graph

GraphData[{"KP",{4,4}},"Line"]

LineGraphQ[GraphData[{"KP",{4,4}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"KP",{4,4}}&]

RootGraph[GraphData[{"KP",{4,4}}]]

RecognizeGraph[%]

Halin

GraphData[{"KP",{4,4}},"Halin"]

GraphData[{"KP",{4,4}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KP",{4,4}},"Rigid"]

GraphData[{"KP",{4,4}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KP",{4,4}},"Flexible"]

GraphData[{"KP",{4,4}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KP",{4,4}},"LCF"]

GraphData[{"KP",{4,4}},"HamiltonianCycleCount"]

GraphData[{"KP",{4,4}},"LCFSignature"]

GraphData[{"KP",{4,4}},"LCFNotations"]

GraphData[{"KP",{4,4}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"KP",{4,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KP",{4,4}}],Debug->True]//Timing

GraphData[{"KP",{4,4}},"Graph","UnitDistance"]//StyleGraphs

UnitDistance by refinement

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

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

Matchstick

GraphData[{"KP",{4,4}},"Matchstick"]

GraphData[{"KP",{4,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KP",{4,4}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"KP",{4,4}},"Polyhedral"]

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

{"KP", {4, 5}}

Names

GraphData[{"KP",{4,5}},"StandardName"]

GraphData[{"KP",{4,5}},"StandardNames"]

Primary

Quit

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KP",{4,5}}]]

Default embedding

g=Graph[GraphData[{"KP",{4,5}},"VertexList"],GraphData[{"KP",{4,5}},"Edges"]]

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

RecognizeGraph@g

GeneralizedPetersen

GraphData[{"KP",{4,5}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

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

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KP",{4,5}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

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

Circular construction

GraphData[{"KP",{4,5}},"Hamiltonian"]

GraphData[{"KP",{4,5}},"LCF"]

GraphData[{"KP",{4,5}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KP",{4,5}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KP",{4,5}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"KP",{4,5}},"Planar"]

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

MinimalCrossing

GraphData[{"KP",{4,5}},{"RCN","CN"}]

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

MinimalCrossingNumber

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

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

(cn=CrossingNumber[GraphData[{"KP",{4,5}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,5}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,5}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,5}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KP",{4,5}},"V"]&]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KP",{4,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KP",{4,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,5}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KP",{4,5}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,5}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,5}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,5}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,5}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KP",{4,5}},"Circulant"]

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

Circulant construction

GraphData[{"KP",{4,5}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KP",{4,5}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KP",{4,5}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KP",{4,5}},"ComplementGraph","Name"]

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"KP",{4,5}},"Line"]

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

RootGraph

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

RootGraph[GraphData[{"KP",{4,5}}]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData[{"KP",{4,5}},"Halin"]

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

Rigid

GraphData[{"KP",{4,5}},"Rigid"]

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

Flexible

GraphData[{"KP",{4,5}},"Flexible"]

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

LCF

GraphData[{"KP",{4,5}},"LCF"]

GraphData[{"KP",{4,5}},"HamiltonianCycleCount"]

GraphData[{"KP",{4,5}},"LCFSignature"]

GraphData[{"KP",{4,5}},"LCFNotations"]

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

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

UnitDistance

GraphData[{"KP",{4,5}},"UnitDistance"]

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

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

UnitDistance by refinement

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

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

Matchstick

GraphData[{"KP",{4,5}},"Matchstick"]

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

3D default

Graph3D[GraphData[{"KP",{4,5}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"KP",{4,5}},"Polyhedral"]

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

{"KP", {4, 6}}

Names

GraphData[{"KP",{4,6}},"StandardName"]

GraphData[{"KP",{4,6}},"StandardNames"]

Primary

GraphData[{"KP",{4,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"KP",{4,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"KP",{4,6}}]]

Default embedding

GraphPlot[Graph[GraphData[{"KP",{4,6}},"VertexList"],GraphData[{"KP",{4,6}},"Edges"]]]

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

RecognizeGraph@g

Degenerate

GraphData[{"KP",{4,6}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"KP",{4,6}},"Graph","Degenerate"]

GeneralizedPetersen

GraphData[{"KP",{4,6}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"KP",{4,6}},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"KP",{4,6}},"Graph","Bilateral"]//StyleGraphs

Grid[DeleteCases[Monitor[{g=#,BilateralGraphEmbeddingTypes[#],GraphSymmetryGroup[#]}&/@GraphData[{"KP",{4,6}},"Graph","All"],g],{_,_,TransformationGroup[{}]}],Dividers->All,Alignment->{{Center,{Left}}}]

Circular

GraphData[{"KP",{4,6}},"Graph","Circular"]//StyleGraphs

Circular construction

GraphData[{"KP",{4,6}},"Hamiltonian"]

GraphData[{"KP",{4,6}},"LCF"]

GraphData[{"KP",{4,6}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"KP",{4,6}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"KP",{4,6}}],#]&/@hc);//Timing

graphswithsymmetrygroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[graphswithsymmetrygroups[[All,-1]]]//Column

(bilaterallyrotatedgraphs={BilaterallyRotatedGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[graphswithsymmetrygroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[symmetricgraphs=DeleteDuplicatesBy[bilaterallyrotatedgraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

symmetricgraphs

gs=symmetricgraphs[[All,1]]

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData[{"KP",{4,6}},"Planar"]

GraphData[{"KP",{4,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"KP",{4,6}},{"RCN","CN"}]

GraphData[{"KP",{4,6}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossingNumber

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"KP",{4,6}}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Select[gs,Max[OuterFace[#]]<=GraphData[{"KP",{4,6}},"V"]&]

(gs=Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"KP",{4,6}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}],Max[OuterFace[#]]<=GraphData[{"KP",{4,6}},"V"]&]])//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Table[MinimalCrossingGraph[GraphData[{"KP",{4,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,1000}]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

GraphData[{"KP",{4,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,6}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"KP",{4,6}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"KP",{4,6}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"KP",{4,6}}],TimeConstraint->10])//AbsoluteTiming

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,6}}],"CrossingNumber"->cn,RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

(gs=Select[Table[MinimalCrossingGraph[GraphData[{"KP",{4,6}}],"CrossingNumber"->(cn=XXX),RandomSeed->i],{i,20000}],!AdjacentCrossingsQ[#,cn]&]//Union)//Timing

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData[{"KP",{4,6}},"V"]],Table[False,cn]],SameTest->Equal]=!=TransformationGroup[{}]&]

Circulant

GraphData[{"KP",{4,6}},"Circulant"]

GraphData[{"KP",{4,6}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"KP",{4,6}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"KP",{4,6}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"KP",{4,6}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"KP",{4,6}},"ComplementGraph","Name"]

Line graph

GraphData[{"KP",{4,6}},"Line"]

LineGraphQ[GraphData[{"KP",{4,6}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"KP",{4,6}}&]

RootGraph[GraphData[{"KP",{4,6}}]]

RecognizeGraph[%]

Halin

GraphData[{"KP",{4,6}},"Halin"]

GraphData[{"KP",{4,6}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"KP",{4,6}},"Rigid"]

GraphData[{"KP",{4,6}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"KP",{4,6}},"Flexible"]

GraphData[{"KP",{4,6}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"KP",{4,6}},"LCF"]

GraphData[{"KP",{4,6}},"HamiltonianCycleCount"]

GraphData[{"KP",{4,6}},"LCFSignature"]

GraphData[{"KP",{4,6}},"LCFNotations"]

GraphData[{"KP",{4,6}},"Graph","LCF"]//StyleGraphs

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

UnitDistance

GraphData[{"KP",{4,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"KP",{4,6}}],Debug->True]//Timing

GraphData[{"KP",{4,6}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"KP",{4,6}},"VertexList"],GraphData[{"KP",{4,6}},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"KP",{4,6}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"KP",{4,6}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{{"KP",{4,6}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"KP",{4,6}}],TimeConstraint->300,"Results"->All]//Timing}

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

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData[{"KP",{4,6}},"Matchstick"]

GraphData[{"KP",{4,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"KP",{4,6}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"KP",{4,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"KP",{4,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"KP",{4,6}},"Polyhedral"]

GraphData[{"KP",{4,6}},"Graph",{"3D","Polyhedron"}]

Gracefulness

p. 22

ungraceful=DeleteCases[RecognizeGraph/@Table[KPGraph[n,2],{n,6,20}],{}]

GraphData[#,"Graceful"]&/@ungraceful

rules=Rule[#,{}]&/@ungraceful

GraphDataCountTable

GraphDataCountTable["KP"]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"KP"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"KP"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"KP"],{n,20}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"KP"],{n,20}]

Antiprism

Entity["Graph",{"Antiprism",n}]["KP"]

seq=Table[GraphData[{"Antiprism",n},"KP"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"KP"],{n,5}]

Barbell

seq=Table[GraphData[{"Barbell",n},"KP"],{n,3,20}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"KP"],{n,20}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"KP"],{n,20}]

Book

seq=Table[GraphData[{"Book",n},"KP"],{n,20}]

Bruhat

seq=Table[GraphData[{"Bruhat",n},"KP"],{n,6}]

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"KP"],{n,20}]

Centipede

seq=Table[GraphData[{"Centipede",n},"KP"],{n,10}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"KP"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["KP"]

seq=Table[GraphData[{"Complete",n},"KP"],{n,30}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["KP"]

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"KP"],{n,20}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["KP"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"KP"],
Piecewise[{{True,Max[m,n]<3}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["KP"]

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"KP"],{n,10}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["KP"]

DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"KP"],
Piecewise[{{True,k==m==n==1}},False]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"KP"],{n,2,12}]

Crown

seq=Table[GraphData[{"Crown",n},"KP"],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["KP"]

seq=Table[GraphData[{"CubeConnectedCycle",n},"KP"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["KP"]

seq=Table[GraphData[{"Cycle",n},"KP"],{n,3,30}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"KP"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"KP"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"KP"],{n,3,20}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"KP"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"KP"],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["KP"]

seq=Table[GraphData[{"Empty",n},"KP"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"KP"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"KP"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"KP"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"KP"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"KP"],{n,3,20}]

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"KP"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"KP"],{n,3,20}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["KP"]

seq=Table[GraphData[{"Grid",{n,n}},"KP"],{n,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["KP"]

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"KP"],
Piecewise[{{True,Min[m,n]<3}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["KP"]

seq=Table[GraphData[{"Grid",{n,n,n}},"KP"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["KP"]

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"KP"],
Piecewise[{{True,Min[k,m,n]==1&&k m n/Max[k,m,n]<3}},False]
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"KP"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"KP"],{n,6}]

Helm

seq=Table[GraphData[{"Helm",n},"KP"],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["KP"]

seq=Table[GraphData[{"Hypercube",n},"KP"],{n,0,10}]

KC

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"KC"],
True
},{n,3,10},{m,10}],1],{_,x_,x_}]

Keller

Entity["Graph",{"Keller",n}]["KP"]

seq=Table[GraphData[{"Keller",n},"KP"],{n,5}]

King n×n

seq=Table[GraphData[{"King",{n,n}},"KP"],{n,20}]

King m×n

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"KP"],
False
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["KP"]

seq=Table[GraphData[{"Knight",{n,n}},"KP"],{n,20}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["KP"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"KP"],
Piecewise[{{True,m==n==1}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

KP

Select[GraphData["KC"],GraphData[#,"KP"]&]

Sort[GraphData[#,"NotationRules","KC"]&/@%]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"KC",{m,n}},"KP"],
Piecewise[{{True,(m==1&&n==3)||(m==1&&n==4)||(m==2&&n==3)}},False]
},{n,3,10},{m,10}],1],{_,x_,x_}]

Ladder

Entity["Graph",{"Ladder",n}]["KP"]

seq=Table[GraphData[{"Ladder",n},"KP"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"KP"],{n,20}]

LindgrenSousselier

seq=Table[GraphData[{"LindgrenSousselier",n},"KP"],{n,11}]

LucasCube

seq=Table[GraphData[{"LucasCube",n},"KP"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"KP"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["KP"]

seq=Table[GraphData[{"MoebiusLadder",n},"KP"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["KP"]

seq=Table[GraphData[{"Mycielski",n},"KP"],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["KP"]

seq=Table[GraphData[{"Odd",n},"KP"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"KP"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["KP"]

seq=Table[GraphData[{"Path",n},"KP"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"KP"],{n,20}]

Pell

seq=Table[GraphData[{"Pell",n},"KP"],{n,9}]

PlummerToft

seq=Table[GraphData[{"PlummerToft",n},"KP"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["KP"]

seq=Table[GraphData[{"Prism",n},"KP"],{n,3,25}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"KP"],{n,20}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"KP"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"KP"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"KP"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"KP"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"KP"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"KP"],{n,5}]

StackedBook

seq=Table[GraphData[{"StackedBook",{n,n}},"KP"],{n,10}]

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"KP"],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["KP"]

seq=Table[GraphData[{"Star",n},"KP"],{n,25}]

Sun

seq=Table[GraphData[{"Sun",n},"KP"],{n,3,20}]

Sunlet

seq=Table[GraphData[{"Sunlet",n},"KP"],{n,3,20}]

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"KP"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"KP"],{n,3,20}]

Transposition

Entity["Graph",{"Transposition",n}]["KP"]

seq=Table[GraphData[{"Transposition",n},"KP"],{n,6}]

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["KP"]

seq=Table[GraphData[{"Trapezohedron",n},"KP"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"KP"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"KP"],{n,0,20}]

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"KP"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"KP"],{n,20}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"KP"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"KP"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"KP"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"KP"],{n,1,20,2}]

Web

seq=Table[GraphData[{"Web",n},"KP"],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["KP"]

seq=Table[GraphData[{"Wheel",n},"KP"],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"KP"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"KP"],{n,2,20}]

WhiteCamel n×n

seq=Table[GraphData[{"Bishop",{n,n}},"KP"],{n,{5}}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"KP"],{n,20}]

GraphData

GraphDataClassString

GraphDataClassString["KP"]

AddIndexedClass

<<MathWorld`Graphs`

rules=Flatten[Table[RecognizeGraph[KPGraph[n,r],"Cache"->"InternalOnly"]->{n,r},{n,30},{r,30}]]

addrules=DeleteCases[rules,HoldPattern[{}->_]]

AddIndexedClass["KP",addrules,"14.3"]

RenameGraphFiles[]

GraphDataString

<<MathWorld`Graphs`

new=Cases[Flatten[Table[RecognizeGraph[KPGraph[n,r],"Cache"->"InternalOnly"]->{n,r},{n,10},{r,10}]],HoldPattern[{}->nr_]:>nr]

Length[new]

todo={{10,6},{10,7},{10,8},{10,9},{10,10}};

file=OpenAppend["~/kp.m"]

WriteString[file,
GraphDataString[KPGraph[#,#2],
"StandardName"->{"KP",{#,#2}},
"Name"->"("<>ToString[#]<>","<>ToString[#]<>")\[Hyphen]KP graph",
"Classes"->{"KP"},
"NotationRules"->{"KP"->{#,#2}},
"Information"->"KPGraph",
"Notation"->Row[{Subscript["K",#1],"\[Square]",Subscript["P",#2]}],
"Skip"->{"Arboricity","BurningNumber","ChromaticPolynomial","ConnectedDominatingSet","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","ConstructionNumber","CoolingNumber","Cycles","CyclicEdgeConnectivity","EmbeddingClasses","ErdosSequence","GracefulLabeling","HadwigerNumber","HamiltonianPaths","IntersectionNumber","IrredundancePolynomial","IrredundantSets","LinklesslyEmbeddable","MatchingGeneratingPolynomial","MaximalIndependentEdgeSet","MaximalIndependentVertexSet","MaximumIndependentEdgeSets","MinimumConnectedDominatingSet","MinimumEdgeCuts","MinimumPathCoverings","MinimumVertexCuts","Minors","ProjectivePlanar","QuadraticEmbeddingConstant","Skewness","Thickness","TuttePolynomial","VertexCuts"},
TimeConstraint->10
]]&@@@todo;

Close[file]