Fleischner Graphs

Author

Eric W. Weisstein
August 15, 2025

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

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

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

Graphic

Graphic

Fleischner=GraphData["Fleischner*"]

GraphicsRow[Show[StyleGraphs@GraphData[#],PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[14,Italic,LightDarkSwitched@Black,FontFamily->"Times"]],PageWidth->140,TextAlignment->Center]]&/@Fleischner,ImageSize->500,Dividers->All,ItemAspectRatio->1]

Sources

Fleischner

Fleischner, H .  ``Uniquely Hamiltonian Graphs of Minimum Degree 4.''  {\it J .\ Graph Th .} {\bf 75}, 167-- 177, 2014

Goedgebeur et al.

Jan Goedgebeur, Barbara Meersman, Carol T. Zamfirescu

https://arxiv.org/pdf/1812.05650

Knuth

Knuth, D.~E.  ``Hamiltonian Paths and Cycles.''  Volume 4, Pre-Fascicle 8A in {\it The Art of Computer Programming.}  Draft, p.~17 and Exercise 120, Aug.~6, 2025.
  \url{https://www-cs-faculty.stanford.edu/~knuth/fasc8a.ps.gz}.\par

Embeddings

<<MathWorld`Graphs`

"FleischnerGraph15"

Names

GraphData["FleischnerGraph15","StandardName"]

GraphData["FleischnerGraph15","StandardNames"]

Fleischner 2014

v={{385,99},{275,101},{419,52},{238,54},{265,206},{398,203},{457,217},{429,234},{345,233},{318,232},{230,233},{206,219},{465,262},{328,279},{196,264}};
g=ScaleGraph@Graph[Range@Length@v,UndirectedEdge@@@{e[3,7,13,14,15,12,4,3,1,9,14,10,2,4],e[15,11,5,1],e[2,6,8,13],{12,11},{7,8},{9,10},{5,6},{13,15}},VertexCoordinates->v,VertexLabels->Automatic]

CurvedEdges[g,{{-.8,13\[UndirectedEdge]15}}]

RecognizeGraph[g]

d=EuclideanDistance@@v[[{4,8}]]/2//FullSimplify

v=Delete[Join[CirclePoints[1/2,5],CirclePoints[5]],8];
v=Join[v,(Normalize[v[[#2]]-v[[#]]]d+v[[#]])&@@@{{8,9},{8,4},{3,5},{3,1},{7,2},{7,6}}];
v[[8]]+={0,1/2};
v[[7]]+={0,1/2};
g=Graph[Range@Length@v,UndirectedEdge@@@{e[9,6,15,7,3,8,10,9,5,2,4,1,13,3,12,5],{1,6},e[4,11,8,7,14,2],{10,11},{12,13},{14,15}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

Primary

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

All

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

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["FleischnerGraph15"]]

Default embedding

GraphPlot[Graph[GraphData["FleischnerGraph15","VertexList"],GraphData["FleischnerGraph15","Edges"],GraphLayout->"HighDimensionalEmbedding"]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData["FleischnerGraph15","Hamiltonian"]

GraphData["FleischnerGraph15","LCF"]

GraphData["FleischnerGraph15","HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["FleischnerGraph15"],#]&/@hc);//Timing

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

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

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

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData["FleischnerGraph15","Planar"]

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["FleischnerGraph15","CN"]

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

MinimalRectilinearCrossing

GraphData["FleischnerGraph15","RCN"]

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

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["FleischnerGraph15"],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["FleischnerGraph15"],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["FleischnerGraph15"],TimeConstraint->1])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,Pi/6]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

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

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

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

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

Circulant

GraphData["FleischnerGraph15","Circulant"]

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

Circulant construction

GraphData["FleischnerGraph15","NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData["FleischnerGraph15","Line"]

LineGraphQ[GraphData["FleischnerGraph15"]]//Timing

RootGraph

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

RootGraph[GraphData["FleischnerGraph15"]]

RecognizeGraph[%]

Halin

GraphData["FleischnerGraph15","Halin"]

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

Rigid

GraphData["FleischnerGraph15","Rigid"]

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

Flexible

GraphData["FleischnerGraph15","Flexible"]

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

LCF

GraphData["FleischnerGraph15","LCF"]

GraphData["FleischnerGraph15","HamiltonianCycleCount"]

GraphData["FleischnerGraph15","LCFSignature"]

GraphData["FleischnerGraph15","LCFNotations"]

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

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

UnitDistance

GraphData["FleischnerGraph15","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

GraphPlot@

RotateGraph[,Pi]

UnitDistance by FindUnitDistanceEmbedding

Table[FindUnitDistanceEmbedding[GraphData["FleischnerGraph15"],MaxIterations->5000,"ReturnWithMessage"->True],20]

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

g=RotateGraph[,{40,79}]

Matchstick

GraphData["FleischnerGraph15","Matchstick"]

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

3D default

Graph3D[GraphData["FleischnerGraph15","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["FleischnerGraph15","Polyhedral"]

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

"FleischnerGraph30"

Names

GraphData["FleischnerGraph30","StandardName"]

GraphData["FleischnerGraph30","StandardNames"]

Primary

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

All

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

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["FleischnerGraph30"]]

Default embedding

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

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

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

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData["FleischnerGraph30","Hamiltonian"]

GraphData["FleischnerGraph30","LCF"]

GraphData["FleischnerGraph30","HamiltonianCycleCount"]

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

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData["FleischnerGraph30"],#]&/@hc);//Timing

circ

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

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

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

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Planar

GraphData["FleischnerGraph30","Planar"]

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["FleischnerGraph30","CN"]

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

MinimalRectilinearCrossing

GraphData["FleischnerGraph30","RCN"]

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

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["FleischnerGraph30"],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["FleischnerGraph30"],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["FleischnerGraph30"],TimeConstraint->1])//AbsoluteTiming

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

GraphPlot@RotateGraph[,2Pi/11]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

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

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

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

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

Circulant

GraphData["FleischnerGraph30","Circulant"]

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

Circulant construction

GraphData["FleischnerGraph30","NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

Line graph

GraphData["FleischnerGraph30","Line"]

LineGraphQ[GraphData["FleischnerGraph30"]]//Timing

RootGraph

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

RootGraph[GraphData["FleischnerGraph30"]]

RecognizeGraph[%]

Halin

GraphData["FleischnerGraph30","Halin"]

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

Rigid

GraphData["FleischnerGraph30","Rigid"]

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

Flexible

GraphData["FleischnerGraph30","Flexible"]

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

LCF

GraphData["FleischnerGraph30","LCF"]

GraphData["FleischnerGraph30","HamiltonianCycleCount"]

GraphData["FleischnerGraph30","LCFSignature"]

GraphData["FleischnerGraph30","LCFNotations"]

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

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

UnitDistance

GraphData["FleischnerGraph30","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

Table[FindUnitDistanceEmbedding[GraphData["FleischnerGraph30"],MaxIterations->5000,"ReturnWithMessage"->True],10]//Timing

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

gs={,};

Matchstick

GraphData["FleischnerGraph30","Matchstick"]

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

3D default

Graph3D[GraphData["FleischnerGraph30","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["FleischnerGraph30","Polyhedral"]

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

Construction

15 vertex

Knuth, D.~E.  ``Hamiltonian Paths and Cycles.''  Volume 4, Pre-Fascicle 8A in The Art of Computer Programming. Draft, p.~17 and Exercise 149, Aug.~6, 2025.
https://www-cs-faculty.stanford.edu/~knuth/fasc8a.ps.gz

Length[verts={"i","j","k","u","v","w","x","y","z","U","V","W","X","Y","Z"}]

edges=Flatten[Partition[#,2,1]&/@StringSplit[StringSplit[StringReplace["i−−−j−−−k−−−i;v−−−i−−−V,w−−−j−−−W,x−−−k−−−X;
u−−−U,v−−−V,w−−−W,x−−−X;u−−−y−−−z,U−−−Y−−−Z;u−−−v,U−−−X;y−−−w,Y−−−W;x−−−z−−−Z−−−V","\n"->""],";"|","],"−−−"],1]

InputForm[edges]

Length[edges]

G0=Graph[verts,UndirectedEdge@@@edges,VertexLabels->Automatic]

RecognizeGraph[G0]

<<MathWorld`Graphs`

HouseOfGraphsLookup[G0]

(hc=FindHamiltonianCycle[G0,All])//Timing

Length[hc]

HighlightGraph[G0,#]&/@hc

pg=GraphAutomorphismGroup[G0]

PermutationList[#,15]&/@GroupElements[pg]

GroupOrder[%]

RotateGraph[,-.3]

Norm@RegionIntersection[Line[v[[{9,4}]]],Line[v[[{12,5}]]]][[1,1]]//FullSimplify

v=Join[CirclePoints[12],CirclePoints[{(Sqrt[2-(Sqrt[3])]),-Pi/2},3]];
g=Graph[Range@Length@v,UndirectedEdge@@@{e[{1,12},1]},VertexCoordinates->v,VertexLabels->Automatic]

Length[v]

FleischnerGraph15=FindCorrespondingGraph[,v]

FleischnerGraph15=;

RecognizeGraph[%]

30 vertex

v=Delete[Join[CirclePoints[1/2,5],CirclePoints[5]],8];
d=1/4;
v=Join[v,(Normalize[v[[#2]]-v[[#]]]d+v[[#]])&@@@{{8,9},{8,4},{3,5},{3,1},{7,2},{7,6}}];
v[[8]]+={0,1/2};
v[[7]]+={0,1/2};
g0=Graph[Range@Length@v,UndirectedEdge@@@{e[9,6,15,7,3,8,10,9,5,2,4,1,13,3,12,5],{1,6},e[4,11,8,7,14,2],{10,11},{12,13},{14,15}},VertexCoordinates->v,VertexLabels->Automatic]

VertexCount[g0]

i

v1=Join[v,{#,-2-#2}&@@@v];
ee=Join[EdgeList[g0],EdgeList[g0]/.i_Integer:>i+15];
g1=Graph[Range@Length@v1,UndirectedEdge@@@ee,VertexCoordinates->v1,VertexLabels->Automatic]

g2=IndexGraph@VertexDelete[g1,6]

v2=GraphEmbedding[g2];
v3=Append[v2,Mean[v2[[{8,23}]]]];
FleischnerGraph30=CenterGraph@EdgeDelete[Graph[Range@Length@v3,Join[EdgeList[g2],UndirectedEdge@@@{e[23,30,8],{19,30},{23,1},{20,14}}],VertexCoordinates->v3,VertexLabels->Automatic],{23\[UndirectedEdge]20,19\[UndirectedEdge]23}]

FleischnerGraph30=;

VertexCount[FleischnerGraph30]

RecognizeGraph@FleischnerGraph30

FindHamiltonianCycle[FleischnerGraph30,All]

Length[%]

VertexConnectivity[FleischnerGraph30]

UnlabelGraph@FleischnerGraph30

GraphData

GraphDataClassString

GraphDataClassString[Intersection@@(GraphData[#,"Classes"]&/@GraphData["Fleischner*"])]

GraphDataString

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

WriteString[file,GraphDataString[FleischnerGraph30,
"StandardName"->"FleischnerGraph30",
"Name"->"Fleischner graph 30",
"Information"->"FleischnerGraphs",
TimeConstraint->10
]]

Close[file]