Hamming Graph

Author

Eric W. Weisstein
May 18, 2026

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

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

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

Figure

hamming=Cases[GraphData["Hamming"],{"Hamming",_}]

GraphicsGrid[
Partition[
Show[With[{g=GraphData[#]},StyleGraphs[#,VertexSize->{"Scaled",.02}]&@If[Lookup[Options[g],GraphLayout]===None,Annotate[g,GraphLayout->"SpringElectricalEmbedding"],g]],PlotLabel->Style[Row[{H,"(",Sequence@@Riffle[#[[2]],", "],")"}],Directive[14,Black,FontFamily->"Times"]]]&/@hamming,
UpTo[4]
],Dividers->All,Alignment->Center,ImageSize->700]

Construction

(Underscript[(Subscript[K, q])□… □(Subscript[K, q]), ⏟]) == {"Hamming", {d, q}}

TextGrid[data=Flatten[Table[{
{d,q},
GraphData[c=RecognizeGraph@Nest[GraphCartesianProduct[CompleteGraph[q],#]&,Graph[{1},{}],d],"NotationRules","Hamming"],
c
},{d,5},{q,2,5}],1],
Dividers->All,Alignment->{{Decimal,Decimal,Left}}]

HammingGraph[5,5]//VertexCount

Properties

Integral

GraphData["Hamming","Integral"]

Classes

TableForm[{ham="Hamming"/.GraphData[#,"NotationRules"],#,RecognizeGraph[HammingGraph@@ham]}&/@
GraphData["Hamming"],TableDepth->2]

TableForm[Flatten[Table[{{d,q},rg=RecognizeGraph[HammingGraph[d,q]],If[rg==={},{},"Hamming"/.GraphData[rg,"NotationRules"]]},{d,4},{q,7}],1],TableDepth->2]

Enumeration

H(2,n)

RecognizeGraph/@Table[HammingGraph[2,n],{n,5}]

Diameter/@Table[HammingGraph[2,n],{n,5}]

H(3,n)

RecognizeGraph/@Table[HammingGraph[3,n],{n,5}]

H(4,n)

RecognizeGraph/@Table[HammingGraph[4,n],{n,5}]

H(5,n)

RecognizeGraph/@Table[HammingGraph[5,n],{n,3}]

H(6,n)

RecognizeGraph/@Table[HammingGraph[6,n],{n,3}]

H(d,1)

RecognizeGraph/@Table[HammingGraph[n,1],{n,2,7}]

H(d,2)

RecognizeGraph/@Table[HammingGraph[n,2],{n,2,7}]

H(d,3)

RecognizeGraph/@Table[HammingGraph[n,3],{n,2,7}]

RecognizeGraph/@Table[UndirectedGraph[CayleyGraph[AbelianGroup[Table[3,{n}]]]],{n,6}]

Embeddings

<<MathWorld`Graphs`

{"Hamming", {3, 3}}

Names

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

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{3,3}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{3,3}},"WikidataID"]

GraphData[{"Hamming",{3,3}},"WikidataID","URL"]

Construction from embedding

This embedding is arlredy in GraphData

Mathematical Games.  Episode 32: Unit Distance Graphs.  Hosted by Ed Pegg Jr.  2025-08-21

"Curiously, the Hamming graphs are not rigid. Here’s a different embedding:"

img=;

DominantColors[img]

g=ImageToUnitDistanceGraph[img,"VertexColor"->]

RecognizeGraph@g

Primary

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

All

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

CurvedEdge

GraphData[{"Hamming",{3,3}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

GraphData[{"Hamming",{3,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Hamming",{3,3}},"Graph","Degenerate"]//Column

Embedding types

GraphDataEmbeddings[GraphData[{"Hamming",{3,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Hamming",{3,3}},"Edges"]

DegenerateGraphEmbeddingTypes@

v=Join[CirclePoints[9],CirclePoints[2/3,9],CirclePoints[{1/3,-Pi/2},9]];
Graph[Range[Length[v]],UndirectedEdge@@@{},VertexCoordinates->v,VertexLabels->Automatic]

g=FindCorrespondingGraph[,v]//Quiet

RecognizeGraph[g]

DegenerateGraphEmbeddingTypes@g

Perspective

GraphData[{"Hamming",{3,3}},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Hamming",{3,3}},"Polyhedron"]

GeneralizedPetersen

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

IGraph

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

Bipartite

GraphData[{"Hamming",{3,3}},"Bipartite"]

GraphData[{"Hamming",{3,3}},"Graph","Bipartite"]//StyleGraphs

CompleteKPartite

GraphData[{"Hamming",{3,3}},"Graph","CompleteKPartite"]//StyleGraphs

Bilateral

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

Circular

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

Circular construction All

GraphData[{"Hamming",{3,3}},"Hamiltonian"]

GraphData[{"Hamming",{3,3}},"LCF"]

GraphData[{"Hamming",{3,3}},"LCFSignature"]

GraphData[{"Hamming",{3,3}},"HamiltonianCycleCount"]

GraphData[{"Hamming",{3,3}},"HamiltonianCycles"]

Planar

GraphData[{"Hamming",{3,3}},"Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{3,3}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,3}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"Hamming",{3,3}},"CN"]

(gs=GraphData[{"Hamming",{3,3}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"Hamming",{3,3}},"RCN"]

GraphData[{"Hamming",{3,3}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"Hamming",{3,3}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"Hamming",{3,3}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalCrossing construction Tutte

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{3,3}},"V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData[{"Hamming",{3,3}},"V"]],
_Integer?(LessEqualThan[GraphData[{"Hamming",{3,3}},"V"]]),
{2}
]],#}&/@TutteGraphs

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"Hamming",{3,3}},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

SymmetricEmbeddingsWithOrientations=DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{3,3}},"V"]])]==0&]

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,3}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,3}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,3}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 1k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"Hamming",{3,3}}],"CrossingNumber"->cn,RandomSeed->n],{n,1000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{3,3}},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"Hamming",{3,3}},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalCrossing construction Random 20k [old]

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

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"Hamming",{3,3}}],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{3,3}},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"Hamming",{3,3}},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

MinimalLocalCrossing

GraphData[{"Hamming",{3,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

GraphData[{"Hamming",{3,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimaRectilinearlLocalCrossing construction 1000

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

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

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

MinimaRectilinearlLocalCrossing construction 20000

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

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

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

Circulant

GraphData[{"Hamming",{3,3}},"Circulant"]

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

Circulant construction

GraphData[{"Hamming",{3,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"Hamming",{3,3}}]])//AbsoluteTiming

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData[{"Hamming",{3,3}},"Line"]

LineGraphQ[GraphData[{"Hamming",{3,3}}]]//Timing

RootGraph

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

RootGraph[GraphData[{"Hamming",{3,3}}]]

Halin

GraphData[{"Hamming",{3,3}},"Halin"]

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

Rigid

GraphData[{"Hamming",{3,3}},"Rigid"]

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

Flexible

GraphData[{"Hamming",{3,3}},"Flexible"]

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

Voltage

GraphData[{"Hamming",{3,3}},"Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{3,3}}],"MaxResults"->20,Debug->True]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF highly symmetric

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,3}}],"MaxResults"->5,Debug->True])//AbsoluteTiming

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,3}}],Method->"Wolfram","MaxResults"->All,"MaxCyclesPerAutomorphism"->All,"MaxPeriod"->Infinity,Debug->True])//AbsoluteTiming

lcf[[All,-1]]//Tally

nicelcf=DeleteCases[lcf,{_,1}]

gs=BilateralLCFGraph@@@nicelcf

EmbeddingClasses/@gs//Column

l={
{{"Hamming",{3,3}},{0,Missing["NotAvailable",nicelcf]}}
};

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

LCF

GraphData[{"Hamming",{3,3}},"LCF"]

GraphData[{"Hamming",{3,3}},"HamiltonianCycleCount"]

GraphData[{"Hamming",{3,3}},"LCFSignature"]

GraphData[{"Hamming",{3,3}},"LCFNotations"]

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

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

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{3,3}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{3,3}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{3,3}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,3}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{3,3}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{3,3}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

<|"Timestamp"->"2026-05-16 12:15:29-0500","ElapsedSeconds"->1440.000751,"LCFSignature"->{{9,2},{3,44},{1,2094704}}|>
(*Completed*)

l1={
{{"Hamming",{3,3}},{0,{{9,2},{3,44},{1,2094704}}}}
};

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,3}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,4,3]

Length[gs]

nicelcf=LCFNotation/@gs

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,3}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

LCF compute random

FindRandomLCFNotation[GraphData[{"Hamming",{3,3}}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],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]

LCF compute 10^6 [2.4 GB]

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

NiceLCFGraphs[LCFNotation/@{,,,,,,},4,3]

LCF compute 10^7 [28.4 GB]

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 5*^7

Tally[(lcf=LCF[GraphData[{"Hamming",{3,3}}],5*^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute all

Divisors[GraphData[{"Hamming",{3,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Hamming",{3,3}}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Hamming",{3,3}},".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

UnitDistance

GraphData[{"Hamming",{3,3}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

gs={RotateGraph[,{97,314}],RotateGraph[,{137,198}]}

UnitDistance construction Vertex-Edge-Degenerate Gerbracht

GraphData[{"Hamming",{3,3}},"Graph","All"][[-1]]

DegenerateGraphEmbeddingTypes[%]

E. Gebracht, May 2008

Embedding due to E. Gerbracht, May 2008

Here's the graph. 9/1 +  9/2 + 9/4.

g3=LinesToGraph[,.1,10^8.]

GraphPlot[g3,Method->None,ImageSize->200]

Vertices[g3]

Degrees[g3]//Union

Vertices[g3]

V[g3]

RecognizeGraph[g3]

GraphData[{"Hamming",{3,3}},"ChromaticNumber"]

ShowLabeledGraph[g3]

Mean/@Map[Norm,#[[All,2]]&/@Split[Sort[{Norm[#],#}&/@Vertices[g3]],Abs[#1[[1]]-#2[[1]]]<.01&],{2}]

FullForm[%]

RootApproximant/@%

Norm/@(Subtract@@@(Edges[g3]/.n_Integer:>Vertices[g3][[n]]))

r=RootApproximant[Vertices[g3],2,Method->{"DegreeCost"->1}];

Norm/@(Subtract@@@(Edges[g3]/.n_Integer:>r[[n]]))//N

Graph[{"Hamming",{3,3}}]//InputForm

g=Graph[{{{1, 2}}, {{1, 3}}, {{1, 4}}, {{1, 7}}, {{1, 10}}, {{1, 19}}, {{2, 3}}, {{2, 5}}, {{2, 8}}, {{2, 11}}, {{2, 20}}, {{3, 6}}, 
  {{3, 9}}, {{3, 12}}, {{3, 21}}, {{4, 5}}, {{4, 6}}, {{4, 7}}, {{4, 13}}, {{4, 22}}, {{5, 6}}, {{5, 8}}, {{5, 14}}, {{5, 23}}, 
  {{6, 9}}, {{6, 15}}, {{6, 24}}, {{7, 8}}, {{7, 9}}, {{7, 16}}, {{7, 25}}, {{8, 9}}, {{8, 17}}, {{8, 26}}, {{9, 18}}, {{9, 27}}, 
  {{10, 11}}, {{10, 12}}, {{10, 13}}, {{10, 16}}, {{10, 19}}, {{11, 12}}, {{11, 14}}, {{11, 17}}, {{11, 20}}, {{12, 15}}, 
  {{12, 18}}, {{12, 21}}, {{13, 14}}, {{13, 15}}, {{13, 16}}, {{13, 22}}, {{14, 15}}, {{14, 17}}, {{14, 23}}, {{15, 18}}, 
  {{15, 24}}, {{16, 17}}, {{16, 18}}, {{16, 25}}, {{17, 18}}, {{17, 26}}, {{18, 27}}, {{19, 20}}, {{19, 21}}, {{19, 22}}, 
  {{19, 25}}, {{20, 21}}, {{20, 23}}, {{20, 26}}, {{21, 24}}, {{21, 27}}, {{22, 23}}, {{22, 24}}, {{22, 25}}, {{23, 24}}, 
  {{23, 26}}, {{24, 27}}, {{25, 26}}, {{25, 27}}, {{26, 27}}}, {{{-1.4619, 0.}}, {{-1.1199, -0.9397}}, {{-1.1199, 0.9397}}, 
  {{-0.7779, 0.}}, {{-0.5959, -0.5}}, {{-0.5959, 0.5}}, {{-0.4771, -0.1736}}, {{-0.4771, 0.1736}}, {{-0.2539, -1.4397}}, 
  {{-0.2539, -0.4397}}, {{-0.2539, 0.4397}}, {{-0.2539, 1.4397}}, {{-0.1351, -0.766}}, {{-0.1351, 0.766}}, {{0.0882, -0.5}}, 
  {{0.0882, 0.5}}, {{0.3889, -0.6736}}, {{0.3889, -0.3264}}, {{0.3889, 0.3264}}, {{0.3889, 0.6736}}, {{0.5077, 0.}}, 
  {{0.731, -1.266}}, {{0.731, -0.266}}, {{0.731, 0.266}}, {{0.731, 1.266}}, {{1.3737, -0.5}}, {{1.3737, 0.5}}}];

unit=GraphData[{"Hamming",{3,3}},"Graph","UnitDistance"][[1]]

v=GraphData[gn={"Hamming",{3,3}},"Embeddings","UnitDistance"][[1]]

EuclideanDistance@@@(GraphData[gn,"Edges","List"]/.i_Integer:>v[[i]])

gs=GraphData[{"Hamming",{3,3}},"Graph",{"Labeled","Degenerate"}]

GraphData[{"Hamming",{3,3}},"Edges"]

DegenerateEmbeddingQ/@gs

Tally[%]

UnitDistance construction Pegg = Gerbracht?

Pegg Cuic Root comp pros NB
Mar 15, 2018

root=Root[1-3 #1+((#1)^3)&,3]; {vals,vals2}=Normal[];
points= Map[Function[x,RootReduce[Sign[x.(root^{0,1,2})](Sqrt[Abs[x.(root^{0,1,2})]])]],vals, {2}];
unitlines=Select[Subsets[points,{2}],Function[x,Chop[N[1-Apply[EuclideanDistance,N[x]]]]==0]];

e=unitlines/.Thread[points->Range[Length[points]]]

g=Graph[Range[Length[points]],UndirectedEdge@@@e,VertexCoordinates->points]

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ[g,WorkingPrecision->∞]

DegenerateGraphEmbeddingTypes@g

Matchstick

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

3D default

Graph3D[GraphData[{"Hamming",{3,3}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Hamming",{3,3}},"Polyhedral"]

{"Hamming", {3, 4}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{3,4}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{3,4}},"WikidataID"]

GraphData[{"Hamming",{3,4}},"WikidataID","URL"]

All

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

Halin

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

LCF

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

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

UnitDistance

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

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

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

Matchstick

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

Bipartite

GraphData[{"Hamming",{3,4}},"Bipartite"]

GraphData[{"Hamming",{3,4}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{3,4}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

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

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

CurvedEdge

GraphData[{"Hamming",{3,4}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,4}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{3,4}},"RCN"]

GraphData[{"Hamming",{3,4}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,4}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,4}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,4}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{3,4}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{3,4}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{3,4}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{3,4}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{3,4}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,4}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{3,4}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{3,4}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{3,4}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,4}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{3,4}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,4}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

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

3D All

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

3D UnitDistance

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

{"Hamming", {3, 5}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{3,5}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{3,5}},"WikidataID"]

GraphData[{"Hamming",{3,5}},"WikidataID","URL"]

All

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

Halin

GraphData[{"Hamming",{3,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,5}},"LCFSignature"]

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

UnitDistance

GraphData[{"Hamming",{3,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,5}}],Debug->True]//Timing

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

Matchstick

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

Bipartite

GraphData[{"Hamming",{3,5}},"Bipartite"]

GraphData[{"Hamming",{3,5}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{3,5}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,5}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"Hamming",{3,5}},{"RCN","CN"}]

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

CurvedEdge

GraphData[{"Hamming",{3,5}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,5}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Cubic",{14,172}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{3,5}},"RCN"]

GraphData[{"Hamming",{3,5}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,5}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,5}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,5}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{3,5}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{3,5}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{3,5}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{3,5}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{3,5}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,5}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{3,5}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{3,5}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{3,5}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,5}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{3,5}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,5}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

Graph3D[GraphData[{"Cubic",{14,172}},"Edges"]]

3D All

GraphData[{"Cubic",{14,172}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Cubic",{14,172}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {3, 6}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{3,6}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{3,6}},"WikidataID"]

GraphData[{"Hamming",{3,6}},"WikidataID","URL"]

All

GraphData[{"Hamming",{3,6}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,6}},"LCFSignature"]

GraphData[{"Hamming",{3,6}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,6}}],Debug->True]//Timing

GraphData[{"Hamming",{3,6}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,6}},"Graph","Matchstick"]//StyleGraphs

Bipartite

GraphData[{"Hamming",{3,6}},"Bipartite"]

GraphData[{"Hamming",{3,6}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{3,6}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,6}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"Hamming",{3,6}},{"RCN","CN"}]

GraphData[{"Hamming",{3,6}},"Graph","MinimalCrossing"]//StyleGraphs

CurvedEdge

GraphData[{"Hamming",{3,6}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{3,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,6}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{3,6}},"RCN"]

GraphData[{"Hamming",{3,6}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,6}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,6}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,6}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{3,6}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{3,6}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{3,6}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{3,6}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{3,6}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,6}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{3,6}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{3,6}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{3,6}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,6}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{3,6}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,6}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

Graph3D[GraphData[{"Hamming",{3,6}},"Edges"]]

3D All

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

3D UnitDistance

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

{"Hamming", {3, 7}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{3,7}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{3,7}},"WikidataID"]

GraphData[{"Hamming",{3,7}},"WikidataID","URL"]

All

GraphData[{"Hamming",{3,7}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{3,7}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{3,7}},"LCFSignature"]

GraphData[{"Hamming",{3,7}},"LCFNotations"]

GraphData[{"Hamming",{3,7}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{3,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{3,7}}],Debug->True]//Timing

GraphData[{"Hamming",{3,7}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Hamming",{3,7}},"Graph","Matchstick"]//StyleGraphs

Bipartite

GraphData[{"Hamming",{3,7}},"Bipartite"]

GraphData[{"Hamming",{3,7}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{3,7}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Hamming",{3,7}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"Hamming",{3,7}},{"RCN","CN"}]

GraphData[{"Hamming",{3,7}},"Graph","MinimalCrossing"]//StyleGraphs

CurvedEdge

GraphData[{"Hamming",{3,7}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{3,7}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{3,7}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{3,7}},"RCN"]

GraphData[{"Hamming",{3,7}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,7}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,7}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{3,7}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{3,7}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{3,7}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{3,7}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{3,7}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{3,7}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{3,7}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{3,7}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{3,7}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{3,7}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,7}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{3,7}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{3,7}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

Graph3D[GraphData[{"Hamming",{3,7}},"Edges"]]

3D All

GraphData[{"Hamming",{3,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Hamming",{3,7}},"Graph",{"3D","UnitDistance"}]

{"Hamming", {4, 3}}

Names

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

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{4,3}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{4,3}},"WikidataID"]

GraphData[{"Hamming",{4,3}},"WikidataID","URL"]

Primary

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

All

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

Construction as CartesianProduct

g=GraphProduct[CycleGraph[3],GraphData[{"Hamming",{4,3}}]]

RecognizeGraph[g]

CurvedEdge

GraphData[{"Hamming",{4,3}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Degenerate

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

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

Embeddings

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

Default embedding

GraphPlot[Graph[GraphData[{"Hamming",{4,3}},"VertexList"],GraphData[{"Hamming",{4,3}},"Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

GeneralizedPetersen

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

IGraph

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

Bipartite

GraphData[{"Hamming",{4,3}},"Bipartite"]

GraphData[{"Hamming",{4,3}},"Graph","Bipartite"]//StyleGraphs

Bilateral

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

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

Circular

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

Circular construction

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

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

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

Planar

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

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{4,3}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData[{"Hamming",{4,3}},"CN"]

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

MinimalRectilinearCrossing

GraphData[{"Hamming",{4,3}},"RCN"]

GraphData[{"Hamming",{4,3}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"Hamming",{4,3}}],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"Hamming",{4,3}}],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

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

Take[gs,UpTo[100]]

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{4,3}},"V"]])]==0&]

Select[tuttegraphs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{4,3}},"V"]])]==1&]

(gs=Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,3}}],"CrossingNumber"->cn,RandomSeed->n]],{n,1000}]//Union)//Timing

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{4,3}},"V"]])]==0&]

Select[gs,Count[OuterFace[#],_?(GreaterThan[GraphData[{"Hamming",{4,3}},"V"]])]==1&]

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

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,3}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,3}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,3}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

GraphData[{"Hamming",{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[{"Hamming",{4,3}}],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

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

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

Circulant construction

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

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

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

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

RootGraph

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

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

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

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

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

Rigid

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

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

Flexible

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

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

Voltage

GraphData[{"Hamming",{4,3}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{4,3}}],"MaxResults"->20,Debug->True]

LCF

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

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

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

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

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

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

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{4,3}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{4,3}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{4,3}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{4,3}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{4,3}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{4,3}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{4,3}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,3}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{4,3}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,3}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

LCF compute random

FindRandomLCFNotation[GraphData[{"Hamming",{4,3}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"Hamming",{4,3}}],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={
{{"Hamming",{4,3}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

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

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"Hamming",{4,3}}],10^6])[[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={
{{"Hamming",{4,3}},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

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

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Hamming",{4,3}},"V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"Hamming",{4,3}},".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

UnitDistance

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

g=RotateGraph[,{389,139}]

Matchstick

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

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

3D default

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

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

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

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

{"Hamming", {4, 4}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{4,4}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{4,4}},"WikidataID"]

GraphData[{"Hamming",{4,4}},"WikidataID","URL"]

All

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

Halin

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

LCF

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

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

UnitDistance

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

Bipartite

GraphData[{"Hamming",{4,4}},"Bipartite"]

GraphData[{"Hamming",{4,4}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{4,4}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

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

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

CurvedEdge

GraphData[{"Hamming",{4,4}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{4,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,4}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{4,4}},"RCN"]

GraphData[{"Hamming",{4,4}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,4}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,4}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,4}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{4,4}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{4,4}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{4,4}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{4,4}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{4,4}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{4,4}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{4,4}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{4,4}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{4,4}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,4}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{4,4}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,4}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

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

3D All

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

3D UnitDistance

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

{"Hamming", {4, 5}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{4,5}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{4,5}},"WikidataID"]

GraphData[{"Hamming",{4,5}},"WikidataID","URL"]

All

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

Halin

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

LCF

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

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

UnitDistance

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

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

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

Matchstick

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

Bipartite

GraphData[{"Hamming",{4,5}},"Bipartite"]

GraphData[{"Hamming",{4,5}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{4,5}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

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

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

CurvedEdge

GraphData[{"Hamming",{4,5}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{4,5}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,5}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{4,5}},"RCN"]

GraphData[{"Hamming",{4,5}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,5}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,5}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,5}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{4,5}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{4,5}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{4,5}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{4,5}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{4,5}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{4,5}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{4,5}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{4,5}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{4,5}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,5}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{4,5}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,5}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

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

3D All

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

3D UnitDistance

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

{"Hamming", {4, 6}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{4,6}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{4,6}},"WikidataID"]

GraphData[{"Hamming",{4,6}},"WikidataID","URL"]

All

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

Halin

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

LCF

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

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

UnitDistance

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

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

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

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

Select[UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Hamming",{4,6}},"Graph",#]&/@{"All","UnitDistance"}),UnitDistanceGraphEmbeddingQ]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

Bipartite

GraphData[{"Hamming",{4,6}},"Bipartite"]

GraphData[{"Hamming",{4,6}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{4,6}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

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

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

CurvedEdge

GraphData[{"Hamming",{4,6}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Hamming",{4,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{4,6}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{4,6}},"RCN"]

GraphData[{"Hamming",{4,6}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,6}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,6}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{4,6}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{4,6}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{4,6}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{4,6}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{4,6}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{4,6}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{4,6}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{4,6}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{4,6}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{4,6}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,6}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{4,6}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{4,6}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

g=Graph[GraphData[{"Hamming",{4,6}},"Edges"]]

3D All

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

3D UnitDistance

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

{"Hamming", {5, 3}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{5,3}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{5,3}},"WikidataID"]

GraphData[{"Hamming",{5,3}},"WikidataID","URL"]

All

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

Halin

GraphData[{"Hamming",{5,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{5,3}},"LCFSignature"]

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

UnitDistance

GraphData[{"Hamming",{5,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{5,3}}],Debug->True]//Timing

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

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

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

UnitDistanceGraphEmbeddingQ[]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

Bipartite

GraphData[{"Hamming",{5,3}},"Bipartite"]

GraphData[{"Hamming",{5,3}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{5,3}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{5,3}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"Hamming",{5,3}},{"RCN","CN"}]

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

CurvedEdge

GraphData[{"Hamming",{5,3}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{5,3}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{5,3}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{5,3}},"RCN"]

GraphData[{"Hamming",{5,3}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,3}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,3}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,3}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{5,3}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{5,3}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{5,3}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{5,3}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{5,3}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{5,3}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{5,3}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{5,3}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{5,3}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{5,3}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{5,3}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{5,3}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

Graph3D[GraphData[{"Hamming",{5,3}},"Edges"]]

3D All

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

3D UnitDistance

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

{"Hamming", {5, 4}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{5,4}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{5,4}},"WikidataID"]

GraphData[{"Hamming",{5,4}},"WikidataID","URL"]

All

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

Halin

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

LCF

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

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

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

UnitDistance

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

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

Bipartite

GraphData[{"Hamming",{5,4}},"Bipartite"]

GraphData[{"Hamming",{5,4}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{5,4}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

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

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

CurvedEdge

GraphData[{"Hamming",{5,4}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

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

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{5,4}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{5,4}},"RCN"]

GraphData[{"Hamming",{5,4}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,4}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,4}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{5,4}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{5,4}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{5,4}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{5,4}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{5,4}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{5,4}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{5,4}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{5,4}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{5,4}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{5,4}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{5,4}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{5,4}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{5,4}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

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

3D All

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

3D UnitDistance

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

{"Hamming", {6, 3}}

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

HouseOfGraphs

hogid=GraphData[{"Hamming",{6,3}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

HouseOfGraphsGraph[hogid]//StyleGraphs[#,ImageSize->Small]&

Wikidata

GraphData[{"Hamming",{6,3}},"WikidataID"]

GraphData[{"Hamming",{6,3}},"WikidataID","URL"]

All

GraphData[{"Hamming",{6,3}},"Graph","All"]//StyleGraphs

Halin

GraphData[{"Hamming",{6,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Hamming",{6,3}},"LCFSignature"]

GraphData[{"Hamming",{6,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Hamming",{6,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Hamming",{6,3}}],Debug->True]//Timing

GraphData[{"Hamming",{6,3}},"Graph","UnitDistance"]//StyleGraphs

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

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

UnitDistanceGraphEmbeddingQ[]

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Hamming",{6,3}},"Graph","Matchstick"]//StyleGraphs

Bipartite

GraphData[{"Hamming",{6,3}},"Bipartite"]

GraphData[{"Hamming",{6,3}},"Graph","Bipartite"]//StyleGraphs

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData[{"Hamming",{6,3}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

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

(cn=CrossingNumber[GraphData[{"Hamming",{6,3}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"Hamming",{6,3}},{"RCN","CN"}]

GraphData[{"Hamming",{6,3}},"Graph","MinimalCrossing"]//StyleGraphs

CurvedEdge

GraphData[{"Hamming",{6,3}},"Graph","CurvedEdge"]//StyleGraphs

Default embedding

g=Graph@GraphData[{"Hamming",{6,3}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Hamming",{6,3}}],"CrossingNumber"->-1]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalRectilinearCrossing

GraphData[{"Hamming",{6,3}},"RCN"]

GraphData[{"Hamming",{6,3}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{6,3}}],
1000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 5k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{6,3}}],
5000,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

MinimalCrossing construction Random 20k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData[{"Hamming",{6,3}}],
20*^3,
"CrossingNumber"->cn,
EdgeShapeFunction->"BezierEdge"
]]//AbsoluteTiming

No crossing points on the boundary:

Length[diagrams0=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==0&],"Graph",{}]]//Timing

Take[diagrams0,UpTo[10]]

One crossing point on the boundary:

Length[diagrams1=Lookup[Select[diagrams,MinimalCrossingOuterCrossingCount[#]==1&],"Graph",{}]]//Timing

Take[diagrams1,UpTo[10]]

graphs=#["Graph"]&/@diagrams;

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[#]
}&/@graphs;//AbsoluteTiming

MaxMemoryUsed[]/10^9.GB

Symmetric embeddings:

Length[SymmetricMinimalEmbeddingData=DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]
]//AbsoluteTiming

SymmetricMinimalEmbeddingData

SymmetricMinimalEmbeddingGraphs=SymmetricMinimalEmbeddingData[[All,1]]

GraphCrossingCount/@SymmetricMinimalEmbeddingGraphs

GraphCrossingDiagram/@SymmetricMinimalEmbeddingGraphs

Voltage

GraphData[{"Hamming",{6,3}},"Graph","Voltage"]//StyleGraphs

VoltageGraphNotation/@gs//Column

Voltage construction

gs=VoltageGraph[GraphData[{"Hamming",{6,3}}],"MaxResults"->20,Debug->True]

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData[{"Hamming",{6,3}}],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData[{"Hamming",{6,3}}],Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData[{"Hamming",{6,3}}],BilateralHamiltonianCycles[[1]]]

LCFNotation@%

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData[{"Hamming",{6,3}}],"MaxResults"->20,Debug->True])//AbsoluteTiming

lcftally=lcf[[All,-1]]//Tally

lcftally[[All,-1]]//Total

gs=NiceLCFGraphs[lcf,all,bilat]

nicelcf=LCFNotation/@gs

nicelcftally=nicelcf[[All,-1]]//Tally

nicelcftally[[All,-1]]//Total

l={
{{"Hamming",{6,3}},{0,Missing["NotAvailable",Cases[nicelcf,{_,_}]]}}
}

PropertyReplace[l,"LCFNotations"]

RenameGraphFiles[]

l2={
{{"Hamming",{6,3}},{0,Missing["NotAvailable",Most@lcftally]}}
}

PropertyReplace[l2,"LCFSignature"]

RenameGraphFiles[]

bilatgs=Select[gs,BilateralGraphEmbeddingQ]

bilatlcf=LCFNotation/@bilatgs;

bilatlcf[[All,-1]]//Tally

LCF compute ssham_lcf

l1={
{{"Hamming",{6,3}},{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

ReverseSort@Tally[(lcf=Import[FileNameJoin[{$GraphDataDirectory,"Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{6,3}},".m.gz"]}]])[[All,2]]]

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{{"Hamming",{6,3}},{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName[{"Hamming",{6,3}},"_bilateral-order-1-reserve.log"]}]]]

BilateralLCFGraph@@@BilateralOrder1LCF//Length//Timing

BilateralLCFGraph@@@Take[BilateralOrder1LCF,10]

Length[bilat=SelectBilateralLCFs[BilateralOrder1LCF,"ProgressEvery"->500,Debug->True]]//Timing

3D default

Graph3D[GraphData[{"Hamming",{6,3}},"Edges"]]

3D All

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

3D UnitDistance

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

Spectra

(2^5)

IntegerSpectrum[HammingGraph[5,2]]//SpectrumForm//TraditionalForm

(2^6)

IntegerSpectrum[HammingGraph[6,2]]//SpectrumForm//TraditionalForm

(2^7)

IntegerSpectrum[HammingGraph[7,2]]//SpectrumForm//TraditionalForm

(2^8)

IntegerSpectrum[HammingGraph[8,2]]//SpectrumForm//TraditionalForm

(3^3)

IntegerSpectrum[HammingGraph[3,3]]//SpectrumForm//TraditionalForm

(3^4)

IntegerSpectrum[HammingGraph[4,3]]//SpectrumForm//TraditionalForm

(3^5)

IntegerSpectrum[HammingGraph[5,3]]//SpectrumForm//TraditionalForm

(3^6)

IntegerSpectrum[HammingGraph[6,3]]//SpectrumForm//TraditionalForm

(3^7)

IntegerSpectrum[HammingGraph[7,3]]//SpectrumForm//TraditionalForm

(4^3)

IntegerSpectrum[HammingGraph[3,4]]//SpectrumForm//TraditionalForm

(4^4)

IntegerSpectrum[HammingGraph[4,4]]//SpectrumForm//TraditionalForm

(4^5)

IntegerSpectrum[HammingGraph[5,4]]//SpectrumForm//TraditionalForm

(4^6)

IntegerSpectrum[HammingGraph[6,4]]//SpectrumForm//TraditionalForm

(5^3)

IntegerSpectrum[HammingGraph[3,5]]//SpectrumForm//TraditionalForm

(5^4)

IntegerSpectrum[HammingGraph[4,5]]//SpectrumForm//TraditionalForm

(5^5)

IntegerSpectrum[HammingGraph[5,5]]//SpectrumForm//TraditionalForm

(6^3)

IntegerSpectrum[HammingGraph[3,6]]//SpectrumForm//TraditionalForm

(6^4)

IntegerSpectrum[HammingGraph[4,6]]//SpectrumForm//TraditionalForm

(7^3)

IntegerSpectrum[HammingGraph[3,7]]//SpectrumForm//TraditionalForm

(7^4)

IntegerSpectrum[HammingGraph[4,7]]//SpectrumForm//TraditionalForm

(8^3)

IntegerSpectrum[HammingGraph[3,8]]//SpectrumForm//TraditionalForm

(8^4)

IntegerSpectrum[HammingGraph[4,8]]//SpectrumForm//TraditionalForm

(9^3)

IntegerSpectrum[HammingGraph[3,9]]//SpectrumForm//TraditionalForm

(10^3)

IntegerSpectrum[HammingGraph[3,10]]//SpectrumForm//TraditionalForm

Minimum vertex coloring

HammingGraphSW[d_,q_]:=(verts=Tuples[Range[q],{d}];
dd=Flatten[Table[{i,j,Count[verts[[i]]-verts[[j]],0]==d-1},{i,Length[verts]-1},{j,i+1,Length@verts}],1];
System`Graph[Range[Length[verts]],UndirectedEdge@@@(Most/@Select[dd,#[[-1]]&])])

H(4,5)

g=HammingGraphSW[4,5];

List@@@EdgeList[g]===GraphData[{"Hamming",{4,5}},"EdgeIndices"]

col[i_]:=Mod[Total[verts[[i]]],5,1];
coloring=col/@Range[5^4]

VertexColoringQ[GraphData[{"Hamming",{4,5}}],coloring]

GraphData

GraphDataClassString

GraphDataClassString["Hamming"]

GraphDataString

ham=Sort["Hamming"/.GraphData[#,"NotationRules"]&/@GraphData["Hamming"]]

new=Select[DeleteCases[Complement[Flatten[Table[{d,q},{d,10},{q,2,6}],1],ham],{1,5}],#[[2]]^#[[1]]<1000&]

newer=Select[new,RecognizeGraph[HammingGraph@@#]==={}&]

IsomorphicGraphQ[DistanceRegularGraph["hamming3.7"],HammingGraph[3,7]]

IsomorphicGraphQ[DistanceRegularGraph["hamming4.6"],HammingGraph[4,6]]

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

Function[{d,q},WriteString[file,GraphDataString[
HammingGraph[d,q],
"StandardName"->{"Hamming",{d,q}},
"Name"->"("<>ToString[d]<>","<>ToString[q]<>")\[Hyphen]Hamming graph",
"Information"->"HammingGraph",
"Classes"->{"DistanceRegular","Hamming"},
"NotationRules"->{"Hamming"->{d,q}},
"Embeddings"->{},
"Skip"->{"Arboricity","Chord","Chords","ChromaticNumber","CliqueCoveringNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","CycleSignature","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","PathPolynomial","RadioNumber","RadioLabeling","RadioLabelings","RectilinearCrossingCount","Skewness","UnitDistance","Thickness"},
TimeConstraint->10
]]]@@@{{3,7},{5,4},{4,6}};

Close["~/hamming.m"]