Accordion Graph

Author

Eric W. Weisstein
December 18, 2022

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

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

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

Source

Accordion graphs: Hamiltonicity, matchings and isomorphism with quartic circulants
John Baptist Gauci, Jean Paul Zerafa
Discrete Applied Mathematics 321 (2022) 126–137

Classes

GraphClassesThatAreClass["Accordion"]

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

Embeddings

<<MathWorld`Graphs`

GraphData["Accordion*"]

{"Accordion", {12, 4}}

GraphData[{"Accordion",{12,4}},"StandardName"]

Primary

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

All

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

Default embedding

GraphPlot@GraphData[{"Accordion",{12,4}},"Edges"]

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

RecognizeGraph[g]

Bilateral

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

Circular

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

Halin

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

LCF

GraphData[{"Accordion",{12,4}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{12,4}},"LCFSignature"]

GraphData[{"Accordion",{12,4}},"LCFNotations"]

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Accordion",{12,4}}],All][[All,All,1]]]//Timing

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

Take[lcf,2]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

UnitDistance

GraphData[{"Accordion",{12,4}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Accordion",{12,4}},{"RCN","CN"}]

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

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{12,4}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{12,4}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{12,4}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{12,4}}],"CrossingNumber"->16]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{12,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{12,4}},"Polyhedral"]

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

{"Accordion", {12, 6}}

GraphData[{"Accordion",{12,6}},"StandardName"]

Primary

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

All

GraphData[{"Accordion",{12,6}},"Graph","All"]//StyleGraphs

Bilateral

GraphData[{"Accordion",{12,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion",{12,6}},"Graph","Circular"]//StyleGraphs

Halin

GraphData[{"Accordion",{12,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{12,6}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{12,6}},"LCFNotations"]

GraphData[{"Accordion",{12,6}},"LCFSignature"]

GraphData[{"Accordion",{12,6}},"Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Accordion",{12,6}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{12,6}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,2]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

UnitDistance

GraphData[{"Accordion",{12,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{12,6}}],Debug->True]//Timing

Matchstick

GraphData[{"Accordion",{12,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{12,6}},{"RCN","CN"}]

GraphData[{"Accordion",{12,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{12,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{12,6}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{12,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{12,6}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{12,6}}],"CrossingNumber"->14]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{12,6}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{12,6}},"Polyhedral"]

GraphData[{"Accordion",{12,6}},"Graph",{"3D","Polyhedron"}]

{"Accordion", {14, 4}}

GraphData[{"Accordion",{14,4}},"StandardName"]

Primary

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

All

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

Bilateral

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

Circular

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

Halin

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

LCF

GraphData[{"Accordion",{14,4}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{14,4}},"LCFSignature"]

GraphData[{"Accordion",{14,4}},"LCFNotations"]

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

LCF compute

Length[FindHamiltonianCycle[GraphData[{"Accordion",{14,4}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{14,4}}],All])[[All,2]]])//Timing

ByteCount[lcf]

nicelcf=Take[lcf,2]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

UnitDistance

GraphData[{"Accordion",{14,4}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Accordion",{14,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Accordion",{14,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{14,4}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{14,4}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{14,4}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{14,4}}],"CrossingNumber"->18]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{14,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{14,4}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"Accordion",{14,4}},"Polyhedron"]}]

{"Accordion", {16, 4}}

GraphData[{"Accordion",{16,4}},"StandardName"]

Primary

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

All

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

Bilateral

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

Circular

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

Halin

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

LCF

GraphData[{"Accordion",{16,4}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{16,4}},"LCFSignature"]

GraphData[{"Accordion",{16,4}},"LCFNotations"]

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{16,4}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{16,4}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,3]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

UnitDistance

GraphData[{"Accordion",{16,4}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Accordion",{16,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Accordion",{16,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{16,4}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,4}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,4}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{16,4}}],"CrossingNumber"->20]]

RecognizeGraph@g

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{16,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{16,4}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"Accordion",{16,4}},"Polyhedron"]}]

{"Accordion", {16, 6}}

GraphData[{"Accordion",{16,6}},"StandardName"]

Primary

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

All

GraphData[{"Accordion",{16,6}},"Graph","All"]//StyleGraphs

Bilateral

GraphData[{"Accordion",{16,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion",{16,6}},"Graph","Circular"]//StyleGraphs

Halin

GraphData[{"Accordion",{16,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{16,6}},"LCFNotations"]

GraphData[{"Accordion",{16,6}},"LCFSignature"]

GraphData[{"Accordion",{16,6}},"Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{16,6}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{16,6}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,4]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

Length[gs]

UnitDistance

GraphData[{"Accordion",{16,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{16,6}}],Debug->True]//Timing

GraphData[{"Accordion",{16,6}},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

{{"Accordion",{16,6}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Accordion",{16,6}}],TimeConstraint->3600,"Results"->All,Debug->Full]//Timing}

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Accordion",{16,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{16,6}},{"RCN","CN"}]

GraphData[{"Accordion",{16,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{16,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{16,6}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,6}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{16,6}}],"CrossingNumber"->26]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{16,6}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{16,6}},"Polyhedral"]

GraphData[{"Accordion",{16,6}},"Graph",{"3D","Polyhedron"}]

{"Accordion", {16, 8}}

GraphData[{"Accordion",{16,8}},"StandardName"]

Primary

GraphData[{"Accordion",{16,8}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Accordion",{16,8}},"Graph","All"]//StyleGraphs

Bilateral

GraphData[{"Accordion",{16,8}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion",{16,8}},"Graph","Circular"]//StyleGraphs

Halin

GraphData[{"Accordion",{16,8}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{16,8}},"LCFSignature"]

GraphData[{"Accordion",{16,8}},"LCFNotations"]

GraphData[{"Accordion",{16,8}},"Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{16,8}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{16,8}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,3]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

Length[gs]

UnitDistance

GraphData[{"Accordion",{16,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{16,8}}],Debug->True]//Timing

Matchstick

GraphData[{"Accordion",{16,8}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{16,8}},{"RCN","CN"}]

GraphData[{"Accordion",{16,8}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{16,8}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{16,8}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,8}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{16,8}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{16,8}}],"CrossingNumber"->18]]

RecognizeGraph@g

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{16,8}},"Edges"]]

3D All

GraphData[{"Accordion",{16,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Accordion",{16,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Accordion",{16,8}},"Polyhedral"]

GraphData[{"Accordion",{16,8}},"Graph",{"3D","Polyhedron"}]

{"Accordion", {18, 4}}

GraphData[{"Accordion",{18,4}},"StandardName"]

Primary

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

All

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

Bilateral

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

Circular

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

Halin

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

LCF

GraphData[{"Accordion",{18,4}},"LCFSignature"]

GraphData[{"Accordion",{18,4}},"LCFNotations"]

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{18,4}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{18,4}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,3]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

Length[gs]

UnitDistance

GraphData[{"Accordion",{18,4}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Accordion",{18,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Accordion",{18,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{18,4}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{18,4}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{18,4}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{18,4}}],"CrossingNumber"->24]]

RecognizeGraph[g]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{18,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{18,4}},"Polyhedral"]

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

Graphics3D[{FaceForm[Green,Red],GraphData[{"Accordion",{18,4}},"Polyhedron"]}]

{"Accordion", {18, 6}}

GraphData[{"Accordion",{18,6}},"StandardName"]

Primary

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

All

GraphData[{"Accordion",{18,6}},"Graph","All"]//StyleGraphs

Bilateral

GraphData[{"Accordion",{18,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion",{18,6}},"Graph","Circular"]//StyleGraphs

Halin

GraphData[{"Accordion",{18,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{18,6}},"LCFSignature"]

GraphData[{"Accordion",{18,6}},"LCFNotations"]

GraphData[{"Accordion",{18,6}},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{18,6}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{18,6}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,2]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}]

Length[gs]

UnitDistance

GraphData[{"Accordion",{18,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{18,6}}],Debug->True]//Timing

GraphData[{"Accordion",{18,6}},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

With[{gn={"Accordion",{18,6}}},
{gn,l=FindSubgraphUnitDistanceEmbedding[GraphData[gn],TimeConstraint->3600,"Results"->All,Debug->Full]//Timing}]

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Accordion",{18,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{18,6}},{"RCN","CN"}]

GraphData[{"Accordion",{18,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{18,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{18,6}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{18,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{18,6}}],TimeConstraint->300]//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{18,6}}],"CrossingNumber"->30]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{18,6}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{18,6}},"Polyhedral"]

GraphData[{"Accordion",{18,6}},"Graph",{"3D","Polyhedron"}]

Graphics3D[{FaceForm[Green,Red],GraphData[{"Accordion",{18,6}},"Polyhedron"]}]

{"Accordion", {20, 4}}

GraphData[{"Accordion",{20,4}},"StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Accordion", {20, 4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Accordion", {20, 4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Accordion", {20, 4}},"Graph","Degenerate"]//StyleGraphs

Bilateral

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

Circular

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

Halin

GraphData[{"Accordion",{20,4}},"Graph","Halin"]

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

LCF

GraphData[{"Accordion",{20,4}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{20,4}},"LCFSignature"]

GraphData[{"Accordion",{20,4}},"LCFNotations"]

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

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{20,4}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{20,4}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,14]

LCFGraph@@@%//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,XX}]]}]

Length[gs]

UnitDistance

GraphData[{"Accordion",{20,4}},"UnitDistance"]

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

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

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

With[{gn={"Accordion",{20,4}}},
{gn,l=FindSubgraphUnitDistanceEmbedding[GraphData[gn],TimeConstraint->3600,"Results"->All,Debug->Full]//Timing}]

gs=UniqueEmbeddings[l]

Matchstick

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

MinimalCrossing

GraphData[{"Accordion",{20,4}},{"RCN","CN"}]

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

Default embedding

GraphPlot@GraphData[{"Accordion",{20,4}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{20,4}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,4}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,4}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{20,4}}],"CrossingNumber"->24]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{20,4}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{20,4}},"Polyhedral"]

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

{"Accordion", {20, 6}}

GraphData[{"Accordion",{20,6}},"StandardName"]

Primary

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

All

GraphData[{"Accordion",{20,6}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Accordion", {20, 6}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Accordion", {20, 6}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Accordion", {20, 6}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Accordion", {20, 6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion", {20, 6}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Accordion", {20, 6}},"Planar"]

GraphData[{"Accordion", {20, 6}},"Graph","Planar"]//StyleGraphs

Halin

GraphData[{"Accordion",{20,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{20,6}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{20,6}},"LCFNotations"]

GraphData[{"Accordion",{20,6}},"LCFSignature"]

GraphData[{"Accordion",{20,6}},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{20,6}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{20,6}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,4]

LCFGraph@@@nicelcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}];

Length[gs]

gs

UnitDistance

GraphData[{"Accordion",{20,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{20,6}}],Debug->True]//Timing

GraphData[{"Accordion",{20,6}},"Graph","UnitDistance"]//StyleGraphs

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

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Accordion",{20,6}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{20,6}},{"RCN","CN"}]

GraphData[{"Accordion",{20,6}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{20,6}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{20,6}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,6}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,6}}],TimeConstraint->300]//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{20,6}}],"CrossingNumber"->34]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{20,6}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Accordion",{20,6}},"Polyhedral"]

GraphData[{"Accordion",{20,6}},"Graph",{"3D","Polyhedron"}]

{"Accordion", {20, 8}}

GraphData[{"Accordion",{20,8}},"StandardName"]

Primary

GraphData[{"Accordion",{20,8}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Accordion",{20,8}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Accordion", {20, 8}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Accordion", {20, 8}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Accordion", {20, 8}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Accordion", {20, 8}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion", {20, 8}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Accordion", {20, 8}},"Planar"]

GraphData[{"Accordion", {20, 8}},"Graph","Planar"]//StyleGraphs

Halin

GraphData[{"Accordion",{20,8}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{20,8}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{20,8}},"LCFNotations"]

GraphData[{"Accordion",{20,8}},"LCFSignature"]

GraphData[{"Accordion",{20,8}},"Graph","LCF"]//StyleGraphs

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{20,8}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{20,8}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,6]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2|4}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,4}]]}];

Length[gs]

gs

UnitDistance

GraphData[{"Accordion",{20,8}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{20,8}}],Debug->True]//Timing

GraphData[{"Accordion",{20,8}},"Graph","UnitDistance"]//StyleGraphs

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

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

FindUnitDistanceEmbedding[GraphData[{"Accordion",{20,8}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"Accordion",{20,8}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{20,8}},{"RCN","CN"}]

GraphData[{"Accordion",{20,8}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{20,8}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{20,8}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,8}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,8}}],TimeConstraint->300]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{20,8}}],"CrossingNumber"->30]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{20,8}},"Edges"]]

3D All

GraphData[{"Accordion",{20,8}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Accordion",{20,8}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Accordion",{20,8}},"Polyhedral"]

GraphData[{"Accordion",{20,8}},"Graph",{"3D","Polyhedron"}]

{"Accordion", {20, 10}}

GraphData[{"Accordion",{20,10}},"StandardName"]

Primary

GraphData[{"Accordion",{20,10}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Accordion",{20,10}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Accordion", {20, 10}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Accordion", {20, 10}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Accordion", {20, 10}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Accordion", {20, 10}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Accordion", {20, 10}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Accordion", {20, 10}},"Planar"]

GraphData[{"Accordion", {20, 10}},"Graph","Planar"]//StyleGraphs

Halin

GraphData[{"Accordion",{20,10}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Accordion",{20,10}},"HamiltonianCycleCount"]

GraphData[{"Accordion",{20,10}},"LCFNotations"]

GraphData[{"Accordion",{20,10}},"LCFSignature"]

GraphData[{"Accordion",{20,10}},"Graph","LCF"]//StyleGraphs

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

LCF compute

Length[FindHamiltonianCycle[GraphData[r={"Accordion",{20,10}}],All][[All,All,1]]]//Timing

(lcfsignature=Tally[(lcf=LCF[GraphData[{"Accordion",{20,10}}],All])[[All,2]]])//Timing

nicelcf=Take[lcf,9]

LCFGraph@@@lcf//StyleGraphs

gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFEmbedding[#],#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1|2}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,2}]]}];

Length[gs]

Take[gs,1+2+2+4]

UnitDistance

GraphData[{"Accordion",{20,10}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Accordion",{20,10}}],Debug->True]//Timing

Matchstick

GraphData[{"Accordion",{20,10}},"Graph","Matchstick"]//StyleGraphs

MinimalCrossing

GraphData[{"Accordion",{20,10}},{"RCN","CN"}]

GraphData[{"Accordion",{20,10}},"Graph","MinimalCrossing"]//StyleGraphs

Default embedding

GraphPlot@GraphData[{"Accordion",{20,10}},"Edges"]

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

RecognizeGraph[g]

MinimalCrossing construction

CrossingNumber[GraphData[{"Accordion",{20,10}}],TimeConstraint->10]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,10}}],TimeConstraint->60]//AbsoluteTiming

CrossingNumber[GraphData[{"Accordion",{20,10}}],TimeConstraint->300]//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Accordion",{20,10}}],"CrossingNumber"->22]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

3D default

Graph3D[GraphData[{"Accordion",{20,10}},"Edges"]]

3D All

GraphData[{"Accordion",{20,10}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Accordion",{20,10}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Accordion",{20,10}},"Polyhedral"]

GraphData[{"Accordion",{20,10}},"Graph",{"3D","Polyhedron"}]

Special cases

A(10, 3)

AccordionGraph[10,3]

A(n, 1) -> Antiprism

RecognizeGraph/@Table[AccordionGraph[n,1],{n,3,10}]

A(n, 2)

RecognizeGraph/@Table[AccordionGraph[n,2],{n,3,20}]

Add to GraphData

A(n, k)

<<MathWorld`Graphs`

all=Sort[Flatten[Table[{n,k,RecognizeGraph@AccordionGraph[n,k]},{n,3,20},{k,1,n/2}],1]]

existing=DeleteCases[all,{n_,k_,{}}]

new=Cases[all,{n_,k_,{}}:>{n,k}]

newcirc=Cases[{{#1,#2},!(EvenQ[#1]&&EvenQ[#2]&&#2>=4)}&@@@new,{i_,True}:>i]

{#,CirculantIndices[AccordionGraph@@#]}&/@newcirc

add=Complement[new,newcirc]

Properties

Bipartite

DeleteCases[Flatten[Table[{n,k,BipartiteGraphQ@AccordionGraph[n,k],EvenQ[n]&&EvenQ[k]},{n,3,20},{k,1,n/2}],1],{_,_,x_,x_}]

Circulant

DeleteCases[{{##},!CirculantGraphQ[AccordionGraph[#,#2]],EvenQ[#1]&&EvenQ[#2]&&#2>=4}&@@@Take[all,60],{_,x_,x_}]//Timing

GraphData

GraphDataString

<<MathWorld`Graphs`

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

add={{20,8},{20,10}};

WriteString[file,GraphDataString[AccordionGraph[#,#2],
"StandardName"->{"Accordion",{#,#2}},
"Name"->"("<>ToString[#]<>","<>ToString[#2]<>")\[Hyphen]accordion graph",
"Information"->"AccordionGraph",
"Classes"->{"Accordion"},
"NotationRules"->{"Accordion"->{#,#2}},
"Skip"->{"ChromaticPolynomial","ConnectedInducedSubgraphPolynomial","TuttePolynomial"},
TimeConstraint->10
]]&@@@add;