Berman Graphs

Author

Eric W. Weisstein
August 1, 2026

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

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

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

Figure

GraphicsRow[Annotate[
StyleGraphs[GraphData[#],VertexSize->{"Scaled",.01}],
PlotLabel->Style[#2,FontFamily->"Times",Italic,14]]&@@@
{
{"Berman485Graph",Row[{"Berman ",Subscript[48,5]," graph"}]},
{"Berman966Graph",Row[{"Berman ",Subscript[96,6]," graph"}]}
},Dividers->All]

Configuration

"Berman485Graph"

GraphData["Berman485Graph","Incidence"]

lines=GraphData["Berman485Graph","Configurations"]

Subscript@@Reverse@Flatten@Tally[Length/@lines[[1]]]

RecognizeGraph[LeviGraph[#]]&/@lines

GraphData["Berman485ConfigurationGraph","#"]

configg=GraphData["Berman485ConfigurationGraph","Graph",{"Configuration","Labeled"}][[1]]

lines2=Sort@ConfigurationLinesFromGraph[configg]

LeviGraph[lines2]//RecognizeGraph

points=GraphEmbedding[configg]

ConfigurationGraph[points,lines2,VertexLabels->Automatic]

RecognizeGraph@%

ConfigurationDiagram[points,lines2]

"Berman966ConfigurationGraph"

GraphData["Berman966Graph","Incidence"]

lines=GraphData["Berman966Graph","Configurations"]

Subscript@@Reverse@Flatten@Tally[Length/@lines[[1]]]

RecognizeGraph[LeviGraph[#]]&/@lines

GraphData["Berman966ConfigurationGraph","#"]

configg=GraphData["Berman966ConfigurationGraph","Graph",{"Configuration","Labeled"}][[1]]

lines2=Sort@ConfigurationLinesFromGraph[configg]

LeviGraph[lines2]//RecognizeGraph

points=GraphEmbedding[configg]

ConfigurationGraph[points,lines2,VertexLabels->Automatic]

RecognizeGraph@%

ConfigurationDiagram[points,lines2]

Embeddings

<<MathWorld`Graphs`

"Berman485Graph"

Names

GraphData["Berman485Graph","StandardName"]

GraphData["Berman485Graph","StandardNames"]

HouseOfGraphs

hogid=GraphData["Berman485Graph","NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData["Berman485Graph","WikidataID"]

GraphData["Berman485Graph","WikidataID","URL"]

Primary

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

All

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

Inexact

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

Degenerate

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

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

Embedding types

GraphDataEmbeddings[GraphData["Berman485Graph","EdgeList"]]

Default embedding

GraphPlot@GraphData["Berman485Graph","Edges"]

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

RecognizeGraph[g]

Incidence

GraphData["Berman485Graph","Incidence"]

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

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

levi=LeviGraph[lines]

RecognizeGraph@levi

Perspective

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

Bipartite

GraphData["Berman485Graph","Bipartite"]

GraphData["Berman485Graph","Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData["Berman485Graph","Bipartite"]

g=BipartiteGraph[GraphData["Berman485Graph"]]

RecognizeGraph@g

Bilateral

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

Circular

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

Planar

GraphData["Berman485Graph","Planar"]

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

Circular construction 1*^5 [1 + 77 s]

Length[hc=FindHamiltonianCycle[GraphData["Berman485Graph"],1*^5][[All,All,1]]]//Timing

Length[hcsym=SymmetricHamiltonianCycles[GraphData["Berman485Graph"],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData["Berman485Graph"],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Circular construction 1*^6 [9 + 756 s]

Length[hc=FindHamiltonianCycle[GraphData["Berman485Graph"],1*^6][[All,All,1]]]//Timing

Length[hcsym=SymmetricHamiltonianCycles[GraphData["Berman485Graph"],hc,ProgressReporting->True]]//Timing

groups=GroupBy[SymmetricHamiltonianCycleGraph[GraphData["Berman485Graph"],#]&/@hcsym,GraphSymmetryGroup]

gs=Join@@Values[groups]

Circular construction All

GraphData["Berman485Graph","Hamiltonian"]

GraphData["Berman485Graph","HamiltonianCycles"]

GraphData["Berman485Graph","HamiltonianCycleCount"]

GraphData["Berman485Graph","LCF"]

GraphData["Berman485Graph","LCFSignature"]

BilateralHamiltonianCycleQ[GraphData["Berman485Graph"]]

FindBilateralHamiltonianCycle[GraphData["Berman485Graph"]]

Planar

GraphData["Berman485ConfigurationGraph","Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData["Berman485Graph"],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["Berman485Graph","CN"]

(gs=GraphData["Berman485Graph","Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData["Berman485Graph","RCN"]

GraphData["Berman485Graph","Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

(g=MinimalCrossingGraph[GraphData["Berman485Graph"],"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["Berman485Graph","V"]])]
}&/@TutteGraphs;

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

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

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

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

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

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

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman485Graph"],
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["Berman485Graph"],TimeConstraint->1])//AbsoluteTiming

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman485Graph"],
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["Berman485Graph"],TimeConstraint->1])//AbsoluteTiming

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman485Graph"],
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

MinimalCrossing construction Random 1k [old]

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

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["Berman485Graph","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["Berman485Graph","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["Berman485Graph"],TimeConstraint->1])//AbsoluteTiming

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["Berman485Graph","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["Berman485Graph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["Berman485Graph"],"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["Berman485Graph"],TimeConstraint->10])//AbsoluteTiming

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

Circulant

GraphData["Berman485Graph","Circulant"]

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

Complement graph

GraphData["Berman485Graph","ComplementGraph","Name"]

Line graph

GraphData["Berman485Graph","Line"]

LineGraphQ[GraphData["Berman485Graph"]]//Timing

RootGraph

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

RootGraph[GraphData["Berman485Graph"]]

Halin

GraphData["Berman485Graph","Halin"]

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

Rigid

GraphData["Berman485Graph","Rigid"]

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

Flexible

GraphData["Berman485Graph","Flexible"]

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

Voltage

GraphData["Berman485Graph","Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData["Berman485Graph"],"MaxResults"->20,Debug->True]

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

GraphData["Berman485Graph","LCF"]

GraphData["Berman485Graph","HamiltonianCycleCount"]

GraphData["Berman485Graph","LCFSignature"]

GraphData["Berman485Graph","LCFNotations"]

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

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

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData["Berman485Graph"],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData["Berman485Graph"],10,Debug->True])//AbsoluteTiming

CircularEmbeddingFromHamiltonianCycle[GraphData["Berman485Graph"],#]&/@BilateralHamiltonianCycles

g=%[[1]]

LCF compute FindHighlySymmetricLCFNotation

lcf=FindHighlySymmetricLCFNotation[GraphData["Berman485Graph"],TimeConstraint->600,Debug->True];//AbsoluteTiming

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

gs=NiceLCFGraphs[lcf,24,12]

nicelcf=LCFNotation/@gs

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

bilatnicelcfgs=Select[gs,BilateralGraphEmbeddingQ]

bilatnicelcf=LCFNotation/@bilatnicelcfgs;

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

l={
{"Berman485Graph",{0,Missing["NotAvailable",Cases[lcfall,{_,24}]]}}
}

l2={
{"Berman485Graph",{0,Missing["NotAvailable",{{24,10},{12,45},{8,802},{6,3765},{5,0}}]}}
}

LCF compute ssham_lcf

l1={
{"Berman485Graph",{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

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

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{"Berman485Graph",{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName["Berman485Graph","_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["Berman485Graph"],TimeConstraint->3600]

LCF compute 10^4

Tally[(lcf=LCF[GraphData["Berman485Graph"],10^4])[[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

LCF compute 10^5

Tally[(lcf=LCF[GraphData["Berman485Graph"],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

LCF compute 10^6

Tally[(lcf=LCF[GraphData["Berman485Graph"],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

LCF compute 10^7

Tally[(lcf=LCF[,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 all

Divisors[GraphData["Berman485Graph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["Berman485Graph",".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["Berman485Graph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["Berman485Graph","Matchstick"]

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

3D default

Graph3D[GraphData["Berman485Graph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["Berman485Graph","Polyhedral"]

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

"Berman966Graph"

Names

GraphData["Berman966Graph","StandardName"]

GraphData["Berman966Graph","StandardNames"]

HouseOfGraphs

hogid=GraphData["Berman966Graph","NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData["Berman966Graph","WikidataID"]

GraphData["Berman966Graph","WikidataID","URL"]

Primary

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

Configuration

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

GraphData["Berman966Graph","Configurations"]

(lines=ResourceFunction["FindExtraordinaryLines"][GraphData["Berman966ConfigurationGraph","VertexCoordinates"]])//Timing

LeviGraph[lines]//RecognizeGraph

All

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

Inexact

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

Degenerate

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

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

Embedding types

GraphDataEmbeddings[GraphData["Berman966Graph","EdgeList"]]

Default embedding

GraphPlot@GraphData["Berman966Graph","Edges"]

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

RecognizeGraph[g]

Incidence

GraphData["Berman966Graph","Incidence"]

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

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

levi=LeviGraph[lines]

RecognizeGraph@levi

Perspective

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

GeneralizedPetersen

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

IGraph

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

CompleteKPartite

GraphData["Berman966Graph","Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData["Berman966Graph","Bipartite"]

GraphData["Berman966Graph","Graph","Bipartite"]//StyleGraphs

Bipartite construction

GraphData["Berman966Graph","Bipartite"]

g=BipartiteGraph[GraphData["Berman966Graph"]]

RecognizeGraph@g

Bilateral

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

Circular

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

Circular construction All

GraphData["Berman966Graph","Hamiltonian"]

GraphData["Berman966Graph","HamiltonianCycles"]

GraphData["Berman966Graph","HamiltonianCycleCount"]

GraphData["Berman966Graph","LCF"]

GraphData["Berman966Graph","LCFSignature"]

BilateralHamiltonianCycleQ[GraphData["Berman966Graph"]]

FindBilateralHamiltonianCycle[GraphData["Berman966Graph"]]

Planar

GraphData["Berman966Graph","Planar"]

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

MinimalCrossingNumber crossings.uos.de

CrossingNumber[GraphData["Berman966Graph"],Method->"WebCompute"]//AbsoluteTiming

DateString[]

Quit

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["Berman966Graph","CN"]

(gs=GraphData["Berman966Graph","Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData["Berman966Graph","RCN"]

GraphData["Berman966Graph","Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalCrossing construction Tutte

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

(g=MinimalCrossingGraph[GraphData["Berman966Graph"],"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["Berman966Graph","V"]])]
}&/@TutteGraphs;

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

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

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

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

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

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

MinimalCrossing construction Random 1k [XXX s]

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

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman966Graph"],
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["Berman966Graph"],TimeConstraint->1])//AbsoluteTiming

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman966Graph"],
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["Berman966Graph"],TimeConstraint->1])//AbsoluteTiming

Length[diagrams=DistinctMinimalCrossingDiagramData[
GraphData["Berman966Graph"],
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

MinimalCrossing construction Random 1k [old]

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

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["Berman966Graph","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["Berman966Graph","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["Berman966Graph"],TimeConstraint->1])//AbsoluteTiming

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["Berman966Graph","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["Berman966Graph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

(gs=Select[Table[MinimalCrossingGraph[GraphData["Berman966Graph"],"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["Berman966Graph"],TimeConstraint->10])//AbsoluteTiming

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

Circulant

GraphData["Berman966Graph","Circulant"]

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

Complement graph

GraphData["Berman966Graph","ComplementGraph","Name"]

Line graph

GraphData["Berman966Graph","Line"]

LineGraphQ[GraphData["Berman966Graph"]]//Timing

RootGraph

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

RootGraph[GraphData["Berman966Graph"]]

Halin

GraphData["Berman966Graph","Halin"]

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

Rigid

GraphData["Berman966Graph","Rigid"]

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

Flexible

GraphData["Berman966Graph","Flexible"]

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

Voltage

GraphData["Berman966Graph","Graph","Voltage"]//StyleGraphs

Voltage construction

gs=VoltageGraph[GraphData["Berman966Graph"],"MaxResults"->50,Debug->True]

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

Length[gs]

RecognizeGraph/@gs

VoltageGraphNotation/@gs//Column

EmbeddingClasses/@gs//Column

GraphSymmetryGroup/@gs//Column

LCF

GraphData["Berman966Graph","LCF"]

GraphData["Berman966Graph","HamiltonianCycleCount"]

GraphData["Berman966Graph","LCFSignature"]

GraphData["Berman966Graph","LCFNotations"]

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

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

LCF compute FindBilateralHamiltonianCycle

BilateralHamiltonianCycleQ[GraphData["Berman966Graph"],Debug->True]//AbsoluteTiming

(BilateralHamiltonianCycles=FindBilateralHamiltonianCycle[GraphData["Berman966Graph"],Debug->True])//AbsoluteTiming

BilateralGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["Berman966Graph"],BilateralHamiltonianCycles[[1]]]

LCF compute FindHighlySymmetricLCFNotation

(lcf=FindHighlySymmetricLCFNotation[GraphData["Berman966Graph"],"MaxResults"->1000,Debug->True])//AbsoluteTiming

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

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

gs=NiceLCFGraphs[lcf,25,12]

gs=LCFGraph@@@Take[lcf,10]

nicelcf=LCFNotation/@gs

l={
{"Berman966Graph",{0,Missing["NotAvailable",nicelcf[[{1}]]]}}
}

LCF compute ssham_lcf

l1={
{"Berman966Graph",{0,sig}}
};

PropertyReplace[l1,"LCFSignature"]

RenameGraphFiles[]

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

gs=NiceLCFGraphs[lcf,3,2]

Length[gs]

nicelcf=LCFNotation/@gs

l2={
{"Berman966Graph",{0,Missing["External",nicelcf]}}
}

PropertyReplace[l2,"LCFNotations"]

RenameGraphFiles[]

Length[BilateralOrder1LCF=Get[FileNameJoin[{"/","Volumes","eww","mma","Graphs","Properties","LCFNotations-Nice",GraphNameToFileName["Berman966Graph","_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["Berman966Graph"],TimeConstraint->3600]

LCF compute 10^4

Tally[(lcf=LCF[GraphData["Berman966Graph"],10^4])[[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

LCF compute 10^5

Tally[(lcf=LCF[GraphData["Berman966Graph"],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

LCF compute 10^6

Tally[(lcf=LCF[GraphData["Berman966Graph"],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

LCF compute 10^7

Tally[(lcf=LCF[,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 all

Divisors[GraphData["Berman966Graph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName["Berman966Graph",".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["Berman966Graph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["Berman966Graph","Matchstick"]

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

3D default

Graph3D[GraphData["Berman966Graph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["Berman966Graph","Polyhedral"]

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