Gritsenko Graph

Author

Eric W. Weisstein
April 30, 2025

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

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

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

Embeddings

<<MathWorld`Graphs`

"GritsenkoGraph"

Names

GraphData["GritsenkoGraph","StandardName"]

GraphData["GritsenkoGraph","StandardNames"]

Primary

GraphData["GritsenkoGraph"]//StyleGraphs[#,ImageSize->Small]&

All

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

Construction from connected component

cc=GraphData["GritsenkoGraph","ConnectedComponents","Name"]

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

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

gs=MyGraphUnion[#,"K1"]&/@GraphData[cc[[1]],"Graph","All"]

RecognizeGraph/@gs

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["GritsenkoGraph"]]

Default embedding

GraphPlot[Graph[GraphData["GritsenkoGraph","VertexList"],GraphData["GritsenkoGraph","Edges"]]]

s=Sqrt[3]/2;
v={};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData["GritsenkoGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["GritsenkoGraph","Graph","Degenerate"]

Configuration

GetGraphData["GritsenkoGraph","File"]

GraphData["GritsenkoGraph","Configuration"]

GraphData["GritsenkoGraph","Graph","Configuration"]//StyleGraphs

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData["GritsenkoGraph","IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData["GritsenkoGraph","LeviGraph","Name"]

FirstCase[GraphData["GritsenkoGraph","StandardNames"],{"Incidence",_}]

Cases[GraphData["GritsenkoGraph","StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData["GritsenkoGraph","OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData["GritsenkoGraph","File"]

GraphData["GritsenkoGraph","Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==="GritsenkoGraph"&]

lines=GraphData["GritsenkoGraph","IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

ProjectionGraph

Manipulate[ProjectionGraph[GraphData["GritsenkoGraph","Graph","3D"],{a,b,c}],{{a,.5},0,1},{{b,.5},0,1},{{c,.5},0,1}]

gs=ProjectionGraph[GraphData["GritsenkoGraph","Graph","3D"],#]&/@{{1/GoldenRatio,0,1},{0,0,1},{1,1,0},{1,1,1}}

Stereographic projection construction

gs=PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],#]&/@{3/2,4}//StyleGraphs

Perspective

GraphData["GritsenkoGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["GritsenkoGraph","Polyhedron"]

PolyhedronGraph[GraphData["GritsenkoGraph","Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{1,0,1},-Pi/2]

PolyhedronProjectionGraph[GraphData["GritsenkoGraph","Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData["GritsenkoGraph","NotationRules","HoneycombToroidal"]

HoneycombToroidal construction...

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,"GritsenkoGraph"}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData["GritsenkoGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

GraphData["GritsenkoGraph","Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData["GritsenkoGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["GritsenkoGraph","Hamiltonian"]

GraphData["GritsenkoGraph","LCF"]

GraphData["GritsenkoGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["GritsenkoGraph"],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["GritsenkoGraph"],#]&/@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["GritsenkoGraph","Planar"]

GraphData["GritsenkoGraph","Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData["GritsenkoGraph"],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData["GritsenkoGraph"]],10]

PlanarGraphEmbeddings

GraphData["GritsenkoGraph","PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData["GritsenkoGraph"],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData["GritsenkoGraph"]]

Tally[ReverseSort[Length/@faces]]

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

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossing

GraphData["GritsenkoGraph",{"RCN","CN"}]

GraphData["GritsenkoGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["GritsenkoGraph"],Automatic,All,Method->"SubgraphIsomorphism",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["GritsenkoGraph"],Automatic,All,Method->"Permutations",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoGraph"],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData["GritsenkoGraph"],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["GritsenkoGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoGraph","V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoGraph","V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData["GritsenkoGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoGraph","V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoGraph","V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["GritsenkoGraph","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["GritsenkoGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["GritsenkoGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData["GritsenkoGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["GritsenkoGraph","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["GritsenkoGraph"],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData["GritsenkoGraph","Circulant"]

GraphData["GritsenkoGraph","Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData["GritsenkoGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["GritsenkoGraph"]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

compl=GraphData["GritsenkoGraph","ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["GritsenkoGraph","Line"]

LineGraphQ[GraphData["GritsenkoGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==="GritsenkoGraph"&]

RootGraph[GraphData["GritsenkoGraph"]]

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

GraphData["GritsenkoGraph","Halin"]

GraphData["GritsenkoGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["GritsenkoGraph","Rigid"]

GraphData["GritsenkoGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["GritsenkoGraph","Flexible"]

GraphData["GritsenkoGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["GritsenkoGraph","LCF"]

GraphData["GritsenkoGraph","HamiltonianCycleCount"]

GraphData["GritsenkoGraph","LCFSignature"]

GraphData["GritsenkoGraph","LCFNotations"]

GraphData["GritsenkoGraph","Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData["GritsenkoGraph"],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData["GritsenkoGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{"GritsenkoGraph",{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData["GritsenkoGraph","V"]]

Length[FindHamiltonianCycle[GraphData["GritsenkoGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["GritsenkoGraph"],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["GritsenkoGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData["GritsenkoGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["GritsenkoGraph"],Debug->True]//Timing

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["GritsenkoGraph","VertexList"],GraphData["GritsenkoGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["GritsenkoGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["GritsenkoGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData["GritsenkoGraph","Matchstick"]

GraphData["GritsenkoGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["GritsenkoGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData["GritsenkoGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["GritsenkoGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["GritsenkoGraph","Polyhedral"]

GraphData["GritsenkoGraph","Graph",{"3D","Polyhedron"}]

"GritsenkoComplementGraph"

Names

GraphData["GritsenkoComplementGraph","StandardName"]

GraphData["GritsenkoComplementGraph","StandardNames"]

Primary

GraphData["GritsenkoComplementGraph"]//StyleGraphs[#,ImageSize->Small]&

All

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

Construction from connected component

cc=GraphData["GritsenkoComplementGraph","ConnectedComponents","Name"]

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

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

gs=MyGraphUnion[#,"K1"]&/@GraphData[cc[[1]],"Graph","All"]

RecognizeGraph/@gs

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["GritsenkoComplementGraph"]]

Default embedding

GraphPlot[Graph[GraphData["GritsenkoComplementGraph","VertexList"],GraphData["GritsenkoComplementGraph","Edges"]]]

s=Sqrt[3]/2;
v={};
g=Graph[Range@Length@v,UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

GraphData["GritsenkoComplementGraph","Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData["GritsenkoComplementGraph","Graph","Degenerate"]

Configuration

GetGraphData["GritsenkoComplementGraph","File"]

GraphData["GritsenkoComplementGraph","Configuration"]

GraphData["GritsenkoComplementGraph","Graph","Configuration"]//StyleGraphs

Configuration...

config=%[[1]]

(alledges=AddAllConfigurationEdges[config])//Timing

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

lines=ConfigurationLines[config]

ConfigurationNotation[lines]

GraphData["GritsenkoComplementGraph","IncidenceLines"]

levi=LeviGraph[lines]

RecognizeGraph[levi]

GraphData["GritsenkoComplementGraph","LeviGraph","Name"]

FirstCase[GraphData["GritsenkoComplementGraph","StandardNames"],{"Incidence",_}]

Cases[GraphData["GritsenkoComplementGraph","StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData["GritsenkoComplementGraph","OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Incidence

GetGraphData["GritsenkoComplementGraph","File"]

GraphData["GritsenkoComplementGraph","Incidence"]

Select[GraphData[All],GraphData[#,"LeviGraph","Name"]==="GritsenkoComplementGraph"&]

lines=GraphData["GritsenkoComplementGraph","IncidenceLines"]

ConfigurationNotation[lines]

levi=LeviGraph[lines]

RecognizeGraph@levi

ProjectionGraph

Manipulate[ProjectionGraph[GraphData["GritsenkoComplementGraph","Graph","3D"],{a,b,c}],{{a,.5},0,1},{{b,.5},0,1},{{c,.5},0,1}]

gs=ProjectionGraph[GraphData["GritsenkoComplementGraph","Graph","3D"],#]&/@{{1/GoldenRatio,0,1},{0,0,1},{1,1,0},{1,1,1}}

Stereographic projection construction

gs=PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],#]&/@{3/2,4}//StyleGraphs

Perspective

GraphData["GritsenkoComplementGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["GritsenkoComplementGraph","Polyhedron"]

PolyhedronGraph[GraphData["GritsenkoComplementGraph","Polyhedron"]]

Manipulate[PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{x,y,z}],{x,-1,1},{y,-1,1},{z,-1,1}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{0,.01,.01}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{0,0,1}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{0,1,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{1,0.01,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{1,1,0}]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{1,0,1},-Pi/2]

PolyhedronProjectionGraph[GraphData["GritsenkoComplementGraph","Polyhedron"],{1,1,1}]

HoneycombToroidal construction

GraphData["GritsenkoComplementGraph","NotationRules","HoneycombToroidal"]

HoneycombToroidal construction...

HoneycombToroidalGraph[1,,]

RecognizeGraph[%]

GeneralizedHoneycombGraph construction

With[{n=},Cases[Table[{k,g=GeneralizedHoneycombGraph[n,k],RecognizeGraph@g},{k,n-1}],{__,"GritsenkoComplementGraph"}]]//Timing

g=GeneralizedHoneycombGraph[,]

RecognizeGraph@g

GeneralizedPetersen

GraphData["GritsenkoComplementGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

GraphData["GritsenkoComplementGraph","Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData["GritsenkoComplementGraph","Graph","Circular"]//StyleGraphs

Circular construction

GraphData["GritsenkoComplementGraph","Hamiltonian"]

GraphData["GritsenkoComplementGraph","LCF"]

GraphData["GritsenkoComplementGraph","HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData["GritsenkoComplementGraph"],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["GritsenkoComplementGraph"],#]&/@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["GritsenkoComplementGraph","Planar"]

GraphData["GritsenkoComplementGraph","Graph","Planar"]//StyleGraphs

Planar construction

PlanarGraphEmbedding[GraphData["GritsenkoComplementGraph"],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData["GritsenkoComplementGraph"]],10]

PlanarGraphEmbeddings

GraphData["GritsenkoComplementGraph","PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData["GritsenkoComplementGraph"],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData["GritsenkoComplementGraph"]]

Tally[ReverseSort[Length/@faces]]

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

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossing

GraphData["GritsenkoComplementGraph",{"RCN","CN"}]

GraphData["GritsenkoComplementGraph","Graph","MinimalCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["GritsenkoComplementGraph"],Automatic,All,Method->"SubgraphIsomorphism",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["GritsenkoComplementGraph"],Automatic,All,Method->"Permutations",Debug->True]]//Timing

Tally[RectilinearCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

gs

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing construction

(cn=CrossingNumber[GraphData["GritsenkoComplementGraph"],TimeConstraint->1])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData["GritsenkoComplementGraph"],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoComplementGraph","V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoComplementGraph","V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData["GritsenkoComplementGraph"],"CrossingNumber"->cn,RandomSeed->n]],{n,50}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoComplementGraph","V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData["GritsenkoComplementGraph","V"]])]==1&]

Select[gs,GraphSymmetryGroup[#,AdditionalData->Join[Table[True,GraphData["GritsenkoComplementGraph","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["GritsenkoComplementGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["GritsenkoComplementGraph","Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData["GritsenkoComplementGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData["GritsenkoComplementGraph","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["GritsenkoComplementGraph"],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData["GritsenkoComplementGraph","Circulant"]

GraphData["GritsenkoComplementGraph","Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData["GritsenkoComplementGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["GritsenkoComplementGraph"]])//Timing

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

compl=GraphData["GritsenkoComplementGraph","ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["GritsenkoComplementGraph","Line"]

LineGraphQ[GraphData["GritsenkoComplementGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==="GritsenkoComplementGraph"&]

RootGraph[GraphData["GritsenkoComplementGraph"]]

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

GraphData["GritsenkoComplementGraph","Halin"]

GraphData["GritsenkoComplementGraph","Graph","Halin"]//StyleGraphs

Rigid

GraphData["GritsenkoComplementGraph","Rigid"]

GraphData["GritsenkoComplementGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["GritsenkoComplementGraph","Flexible"]

GraphData["GritsenkoComplementGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["GritsenkoComplementGraph","LCF"]

GraphData["GritsenkoComplementGraph","HamiltonianCycleCount"]

GraphData["GritsenkoComplementGraph","LCFSignature"]

GraphData["GritsenkoComplementGraph","LCFNotations"]

GraphData["GritsenkoComplementGraph","Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData["GritsenkoComplementGraph"],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData["GritsenkoComplementGraph"],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{"GritsenkoComplementGraph",{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData["GritsenkoComplementGraph","V"]]

Length[FindHamiltonianCycle[GraphData["GritsenkoComplementGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["GritsenkoComplementGraph"],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["GritsenkoComplementGraph",".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

LCFGraph@@@DeleteCases[lcf,{_,1}]//StyleGraphs

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

i=0;
gs={};
t0=AbsoluteTime[];
count=Length[order2];
Monitor[
Do[
If[!MissingQ[g=BilateralLCFGraph[LCFGraph@@order2[[i]]]],AppendTo[gs,g]],
{i,count}
],
Column[{
ProgressIndicator[i,{1,count}],
Row[{i,"/",count}],
Row[{"estimated time remaining: ",Round[(AbsoluteTime[]-t0) (count/i-1)]," s"}],
Row[{Length[gs]," bilateral graphs"}]
}]
];//Timing

UnitDistance

GraphData["GritsenkoComplementGraph","UnitDistance"]

UnitDistanceGraphQ[GraphData["GritsenkoComplementGraph"],Debug->True]//Timing

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["GritsenkoComplementGraph","VertexList"],GraphData["GritsenkoComplementGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["GritsenkoComplementGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData["GritsenkoComplementGraph"],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData["GritsenkoComplementGraph","Matchstick"]

GraphData["GritsenkoComplementGraph","Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData["GritsenkoComplementGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData["GritsenkoComplementGraph","Graph",{"3D","All"}]

3D UnitDistance

GraphData["GritsenkoComplementGraph","Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData["GritsenkoComplementGraph","Polyhedral"]

GraphData["GritsenkoComplementGraph","Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData["GritsenkoComplementGraph","Polyhedron"]}]

3D Canonical

GraphData["GritsenkoComplementGraph","Graph",{"3D","Canonical"}]

Graphics3D[{Opacity[.5],Red,GraphData["GritsenkoComplementGraph","Polyhedron","Canonical"],Yellow,Sphere[]}]

Construction

Gritsenko 2021

https://arxiv.org/abs/2102.05432

adj=;

g=AdjacencyGraph[ToExpression[Characters/@StringSplit[adj]]]

RecognizeGraph@g

DistanceRegular.org

g=DistanceRegularGraph["gritsenko.am"]

RecognizeGraph@g

RecognizeGraph@GraphComplement@g

StronglyRegularGraphQ[g]

RegularParameters[g]

IntersectionArray[g]

DistanceTransitiveGraphQ[g]

CharacteristicPolynomialToSpectrum[CharacteristicPolynomial[AdjacencyMatrix[g],x],x]//SpectrumForm//TraditionalForm

adj=;

IsomorphicGraphQ[AdjacencyGraph[ToExpression[Characters/@StringSplit[adj]]],g]

GraphData

GraphDataClassString

GraphDataClassString["GritsenkoGraph"]

GraphDataString

<<MathWorld`Graphs`

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

WriteString[
file,
GraphDataString[
,
"Embeddings"->{},
"StandardName"->"GritsenkoGraph",
"Name"->"Gritsenko graph",
"Information"->"GritsenkoGraph",
"Skip"->{"Anarboricity","Arboricity","ChordlessCycles","CirculantIndices","ComplementChordlessCycles","ConnectedInducedSubgraphPolynomial","ConstructionNumber","CyclicEdgeConnectivity","EdgeCovers","IdiosyncraticPolynomial","IndependentEdgeSets","IrredundancePolynomial","MatchingGeneratingPolynomial","MaximalIndependentEdgeSet","MaximumIndependentEdgeSets","MaximumIndependentEdgeSetCount","MetricDimension","MinimumConnectedDominatingSets","MinimumCyclicEdgeCuts","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexColorings","MinimumVertexCut","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","Minors","TotalDominationPolynomial","TotalDominatingSets","TuttePolynomial"}
]]

Close[file]