LCF Notation

Author

Eric W. Weisstein
October 30, 2017

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

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

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

Counts

All == Connected

A283825

0, 0, 1, 2, 2, 5, 4, 17, 22, 165, 538, 18972, 389426, 50314715

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","LCF"}]]

Length/@Table[Select[Graphs[n],LCFGraphQ],{n,8}]//Timing

Length/@Table[GraphData["LCF",n],{n,10}]

Cubic

A001186

1, 2, 5, 17, 80, 474, 3841, 39635, 495991, 7170657, 116171803, 2070451150

Length/@Table[GraphData[{"Cubic","LCF"},n],{n,16}]

Length/@Table[GraphData[{"Cubic","LCF"},n],{n,16}][[2;;;;2]]

Example Figure

ShowGraph[LCFNotation[{3,-3},4],ImageSize->200]

Enumerate LCF graphs

Cubic

Length/@Table[GraphData[{"LCF","Cubic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[3,n,Method->"WebImport"]/.$Failed->{},HamiltonianGraphQ],{n,11}]

Length/@Table[Select[RegularGraphs[3,n],HamiltonianGraphQ],{n,11}]

Quartic

Length/@Table[GraphData[{"LCF","Quartic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[4,n,Method->"WebImport"],HamiltonianGraphQ],{n,11}]

Length/@Table[Select[RegularGraphs[4,n],HamiltonianGraphQ],{n,11}]

Length/@Table[GraphData[{"Connected","Quartic"},n],{n,11}]

Quintic

Length/@Table[GraphData[{"LCF","Quintic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[5,n,Method->"WebImport"],HamiltonianGraphQ],{n,11}]

Sextic

Length/@Table[GraphData[{"LCF","Sextic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[6,n,Method->"WebImport"],HamiltonianGraphQ],{n,11}]

Length/@Table[Select[RegularGraphs[6,n],HamiltonianGraphQ],{n,11}]

Septic

Length/@Table[GraphData[{"LCF","Septic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[7,n],HamiltonianGraphQ],{n,11}]

Octic

Length/@Table[GraphData[{"LCF","Octic"},n],{n,11}]

Length/@Table[Select[RegularGraphs[8,n],HamiltonianGraphQ],{n,11}]

add=Cases[(ToEntity/@Select[RegularGraphs[8,11],HamiltonianGraphQ]),ToEntity[g_]:>g]//Quiet

Apply[List,EdgeList/@add,{2}]

Table

# LCF notations  = # Hamiltonian cycles

Length[l=Monitor[Select[GraphData["LCF"],ListQ[lcf=GetGraphData[g=#,"LCF"]]&&Length[lcf]===GetGraphData[#,"HamiltonianCycleCount"]&],g]]//Timing

All LCF cycles are of order 1

Length[l=Monitor[Select[GraphData["LCF"],ListQ[lcf=GetGraphData[g=#,"LCF"]]&&Union[Last/@lcf]==={1}&],g]]//Timing

l

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

Cubic

TableForm[{GraphData[#,"Name"],GraphData[#,"VertexCount"],First["LCF"/.GraphData[#,"NotationRules"]]}&/@Sort[GraphData["LCF"],GraphData[#1,"VertexCount"]<=GraphData[#2,"VertexCount"]&],TableDepth->2]

Short Periodicities

$DataFile="/Volumes/Users/eww/Mathematica/Paclets/GraphData/GraphData.m";

Length[lines=ReadList[$DataFile,"String"]]//Timing//AbsoluteTiming

(alllcf=DeleteCases[DeleteCases[Identity@@@(StringReplace[#,RegularExpression["RawGraphData\[(.*),\"NotationRules\"\]:=(.*)"]:>{"$1","LCF"/.ToExpression["$2"]}]&/@Cases[lines,_?(StringMatchQ[#,"*\",\"NotationRules\"*"]||StringMatchQ[#,"*},\"NotationRules\"*"]&)]),
{_,"LCF"}]/.Missing["NotAvailable",l_List]:>{l},
{_,_Missing}])//Length//Timing

LCFTable[n_]:=Module[{l=Select[alllcf,MemberQ[Length/@First/@Last[#],n]&]},
Function[f,{f[[1]],Select[f[[2]],Length[First[#]]==n&]}]/@l
]

LCFTable[n_]:=Module[{lcf=Select[GraphData["LCFSignature","Defined"],MatchQ[GraphData[#,"LCFNotations"],_List|Missing[_,_List]]&]},
DeleteCases[Function[g,{g,Select[GraphData[g,"LCFNotations"]/.Missing[_,l_]:>l,Length[#[[1]]]==n&]}]/@lcf,{_,{}}]
]

Lentgth 1 only

Select[GraphData["LCFSignature","Defined"],MatchQ[GraphData[#,"LCFSignature"],{{1,_}}]&]

Length 1

Table

Grid[DeleteCases[LCFTable[1],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Length 2

Table

Grid[Take[LCFTable[2],All],Dividers->All,Alignment->Left]

Search

LCFSearch/@GraphData["LCF"]

Length 3

Table

Grid[DeleteCases[LCFTable[3],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Length 4

Grid[DeleteCases[LCFTable[4],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Length 5

Grid[DeleteCases[LCFTable[5],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Length 6

Grid[DeleteCases[LCFTable[6],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Search

RotateUntilMatch1[l_]:=NestWhileList[RotateLeft,l,!MatchQ[#,{k1_,l1_,m1_,m2_,l2_,k2_}/;Abs[m2]==Abs[m1]&&Abs[l2]==Abs[l1]&&Abs[ k2]==Abs[k1]]&,1,6]
RotateUntilMatch2[l_]:=NestWhileList[RotateLeft,l,!MatchQ[#,{k1_,l1_,l2_,m1_,m2_,k2_}/;Abs[m2]==Abs[m1]&&Abs[l2]==Abs[l1]&&Abs[ k2]==Abs[k1]]&,1,6]
RotateUntilMatch3[l_]:=NestWhileList[RotateLeft,l,!MatchQ[#,{k1_,l1_,m1_,k2_,m2_,l2_}/;Abs[m2]==Abs[m1]&&Abs[l2]==Abs[l1]&&Abs[ k2]==Abs[k1]]&,1,6]

FindRotation[l_,rot_]:=Module[{r=rot[l],lp},
If[(First[r]==l&&Length[r]==1)||Length[r]<6,Return[Last[r]]];
r=rot[lp=-Reverse[l]];
If[(First[r]==lp&&Length[r]==1)||Length[r]<6,Last[r],$Failed]
]

FindRotation[#,RotateUntilMatch1]&/@Reverse/@First/@Flatten[Last/@LCFTable[6],1]//ColumnForm

FindRotation[#,RotateUntilMatch2]&/@Reverse/@First/@Flatten[Last/@LCFTable[6],1]//ColumnForm

FindRotation[#,RotateUntilMatch3]&/@Reverse/@First/@Flatten[Last/@LCFTable[6],1]//ColumnForm

Length 7

Grid[DeleteCases[LCFTable[7],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Length 8

Grid[DeleteCases[LCFTable[8],{{"Circulant"|"Complete",_},_}],Dividers->All,Alignment->Left]

Checks

Take[Reverse@Sort[{Total[GraphData[#,"LCFSignature"][[All,2]]],#}&/@Select[GraphData["LCF",;;12],Head[GraphData[#,"LCFSignature"]]=!=Missing&]],10]

Compare code to GraphData

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;10],{_,x_,x_}|{_,_Missing,_}]//Timing

Profiling

Original Code

(lcf0=LCF[GraphData["Q4"],All]);//Timing

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;9],{_,x_,x_}|{_,_Missing,_}]//Timing

Length[hc=FindHamiltonianCycle[GraphData[g={"Circulant",{12,{1,3,4,6}}}],All][[All,All,1]]]//Timing

Length[lcf0=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

Using Compiled MinimalLength

Using MinimalBy

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;10],{_,x_,x_}|{_,_Missing,_}]//Timing

Default target

Length[lcf2=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

lcf2===lcf0

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;10],{_,x_,x_}|{_,_Missing,_}]//Timing

C

Length[lcf1=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

lcf1===lcf0

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;10],{_,x_,x_}|{_,_Missing,_}]//Timing

Fourier Shortest Period

Using FromDigits

Clear[ShortestPeriod]

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=FromDigits/@l0,p},
Print[l];
p=Length[DeleteCases[Chop[Fourier[l]],0]];
{Take[l0,p],n/p}]

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

(lcf1=LCF[GraphData["Q4"],All]);//Timing

lcf1==lcf0

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;9],{_,x_,x_}|{_,_Missing,_}]//Timing

Using Hash

Clear[ShortestPeriod]

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=Hash/@l0,p},
Print[l];
p=Length[DeleteCases[Chop[Fourier[l]],0]];
{Take[l0,p],n/p}]

Length[lcf1=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

Length[lcf1=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

Length[lcf1=LCF[List@@@EdgeList[GraphData[g]],hc,All]]//Timing

lcf0==lcf1

(lcf2=LCF[GraphData["Q4"],All]);//Timing

lcf2==lcf0

DeleteCases[{#,GraphData[#,"LCFNotations"],LCF[GraphData[#],All]}&/@GraphData["LCF",2;;9],{_,x_,x_}|{_,_Missing,_}]//Timing

LCFMinimal disabled

LCF[q,All];//Timing

ShortestPeriod

Disabled

LCF[q,All];//Timing

Smallest to biggest

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=l0,d,i=1},d=Divisors[n];
While[!SameQ@@Partition[l,d[[i]]],i++];
{Take[l0,d[[i]]],n/d[[i]]}]

lcf1=LCF[q,All];//Timing

With replacement

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=l0/.MapIndexed[(#->#2[[1]])&,Union[l0]],d,i=1},d=Divisors[n];
While[!SameQ@@Partition[l,d[[i]]],i++];
{Take[l0,d[[i]]],n/d[[i]]}]

lcf3=LCF[q,All];//Timing

lcf1==lcf3

With hashing

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=Hash/@l0,d,i=1},d=Divisors[n];
While[!SameQ@@Partition[l,d[[i]]],i++];
{Take[l0,d[[i]]],n/d[[i]]}]

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

lcf4=LCF[q,All];//Timing

lcf1==lcf4

With caching and hashing

Clear[LCFMinimalShortestPeriod]

LCFMinimalShortestPeriod[l0_]:=LCFMinimalShortestPeriod[l0]=Block[{n=Length[l0],l=Hash/@l0,d,i=1},d=Divisors[n];
While[!SameQ@@Partition[l,d[[i]]],i++];
LCFMinimal@@{Take[l0,d[[i]]],n/d[[i]]}]

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

lcf3=LCF[GraphData["Q4"],All];//Timing

lcf3==lcf0

With caching before and after and hashing

g=GraphData[{"Circulant",{10,{1,2,3,5}}}];

Total[Table[LCF[g,All];//Timing,{10}][[All,1]]]/10.

Total[Table[LCF[g,All];//Timing,{10}][[All,1]]]/10.

Total[Table[LCF[g,All];//Timing,{10}][[All,1]]]/10.

Total[Table[LCF[g,All];//Timing,{10}][[All,1]]]/10.

lcf2=LCF[GraphData["Q4"],All];//Timing

lcf2==lcf0

Tally[lcf2[[All,2]]]

Partition code without hashing

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=l0,d,i=1,parts},d=Divisors[n];parts=Partition[l,#]&/@d;
pos=Position[parts,_?(SameQ@@#&),{1},1,Heads->False][[1,1]];
{parts[[pos,1]],n/d[[pos]]}
]

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

lcf7=LCF[q,All];//Timing

lcf1===lcf7

Partition code with hashing

ShortestPeriod[l0_]:=Block[{n=Length[l0],l=Hash/@l0,d,i=1,parts},d=Divisors[n];parts=Partition[l,#]&/@d;
pos=Position[parts,_?(SameQ@@#&),{1},1,Heads->False][[1,1]];
{Take[l0,d[[pos]]],n/d[[pos]]}
]

ShortestPeriod[{{-2,2},{-2,2},{-2,2},{-2,2},{-2,2},{-2,2}}]

lcf2=LCF[q,All];//Timing

lcf1===lcf2

LCFMinimal and ShortestPeriod disabled

LCF[q,All];//Timing

Search

Initialization

LCFMinimal[l_,n_]:={Sort[Join@@({#,-Reverse[#]}&/@NestList[RotateRight,l,Length[l]-1])][[1]],n}

LCFSearch[g_,2]:=Module[{v=V[g],i,c=CanonicalForm[g]},
Monitor[Do[
If[c===CanonicalForm[LCFNotation[{i,-i},v/2]],Return[{{i,-i},v/2}]],{i,If[OddQ[v/2],0,1]-v/2,-2,2}],{i,-i}]
]
LCFSearch[g0_,3]:=Module[{v,g,i1,i2,c},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&c===CanonicalForm[LCFNotation[{i1,i2,-i2},v/3]],Return[{{i1,i2,-i2},v/3}]],
{i1,-Floor[v/2],-2},
{i2,Max[i1,1-Floor[v/2]],Floor[(v-1)/2]}
],
{g0,{i1,i2,-i2}}]
]
LCFSearch[g0_,4]:=Module[{v,g,i1,i2,c},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&Abs[i1]>1&&c===CanonicalForm[LCFNotation[{i1,-i1,i2,-i2},v/4]],Return[LCFMinimal[{i1,-i1,i2,-i2},v/4]]],
{i1,-Floor[v/2],Floor[v/2]},{i2,Max[i1,1-Floor[v/2]],Floor[(v-1)/2]}
],
{g0,{i1,-i1,-i2,i2}}]
]
LCFSearch[g0_,5]:=Module[{v,g,i1,i2,i3,c},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Quiet@Do[
If[Abs[i1]>1&&Abs[i3]>1&&c===CanonicalForm[LCFNotation[{i1,i2,-i2,-i1,i3},v/5]],Return[LCFMinimal[{i1,i2,-i2,-i1,i3},v/5]]],
{i1,-Floor[v/2],Floor[(v-1)/2]},
{i2,-Sign[i1]2,-Sign[i1]Floor[v/2],If[i1==0,1,-Sign[i1]]},
{i3,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i2,-i2,-i1,i3}}]
]

LCFSearch[g0_,6]:=Module[{v,g,i1,i2,i3,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Quiet@Do[
If[Abs[i1]>1&&Abs[i2]>1&&Abs[i3]>1&&!(i1==-i2==i3)&&CubicQ[l=LCFNotation[{i1,i2,i3,-i3,-i2,-i1},v/6]]&&c===CanonicalForm[l],Return[{{i1,i2,i3,-i3,-i2,-i1},v/6}]],
{i1,-Floor[v/2],Floor[(v-1)/2]},
{i2,-Floor[v/2],Floor[v/2]},
{i3,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i2,i3,-i3,-i2,-i1}}]
]

p=Permutations[{i,i,j,j,k,k}];

l=Flatten[Outer[List,Sequence@@Table[{-1,1},{6}]],5];

perms=Union[Flatten[Outer[Times,p,l,1],1]];

LCFMinimal6[l_]:=Sort[Join@@({#,-Reverse[#]}&/@NestList[RotateRight,l,Length[l]-1])][[1]]

LCFSearch[g0_,6]:=Module[{v,g,c},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Union[LCFMinimal6/@Union[Flatten[Table[perms,{i,2,v/2},{j,2,v/2},{k,2,v/2}],2]]]
]

perms[[1]]

LCFSearch["Foster024A",6]

Length 2

lcf=Last/@Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData["LCF"],("LCF"/.GraphData[#,"NotationRules"])===Missing["NotAvailable"]&&Mod[GraphData[#,"VertexCount"],2]==0&]]

{#,LCFSearch[Graph[#],2]//Timing}&/@Cases[lcf,{"CrossedPrism",_}]

Print[{#,LCFSearch[Graph[#],2]//Timing}]&/@Select[Cases[lcf,_String],StringMatchQ[#,"Foster"~~__]&&OddQ[GraphData[#,"VertexCount"]/2]&];

Print[{#,LCFSearch[Graph[#],2]//Timing}]&/@Select[Cases[lcf,_String],StringMatchQ[#,"Foster"~~__]&&GraphData[#,"VertexCount"]≥806&&OddQ[GraphData[#,"VertexCount"]/2]&];

Print[{#,LCFSearch[Graph[#],2]//Timing}]&/@Select[Cases[lcf,_String],StringMatchQ[#,"Foster"~~__]&&GraphData[#,"VertexCount"]≥962&&OddQ[GraphData[#,"VertexCount"]/2]&];

Length 2 exhaustive

LCFSearchExhaustive[g0_,2]:=Module[{v,g,i1,i2,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[CubicQ[l=LCFNotation[{i1,i2},v/2]]&&c===CanonicalForm[l],Return[{{{i1,i2},v/2},LCFMinimal[{i1,i2},v/2]}]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i2}}]
]

lcf=Last/@Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData["LCF"],("LCF"/.GraphData[#,"NotationRules"])===Missing["NotAvailable"]&&Mod[GraphData[#,"VertexCount"],2]==0&]]

Print[{#,LCFSearchExhaustive[#,2]//Timing}]&/@Cases[lcf,{"CrossedPrism",_}];

Print[{#,LCFSearchExhaustive[#,2]//Timing}]&/@Cases[lcf,{"Cage",_}];

Print[{#,LCFSearchExhaustive[#,2]//Timing}]&/@lcf;

Print[{#,LCFSearchExhaustive[#,2]//Timing}]&/@Select[Cases[lcf,_String],StringMatchQ[#,"Foster"~~__]&&GraphData[#,"VertexCount"]>=220&];

Length 3

lcf=Select[GraphData["LCF"],Mod[GraphData[#,"VertexCount"],3]==0&];

Print[{#,LCFSearch[#,3]//Timing}]&/@Cases[lcf,{"Cage",_}]

Print[{#,LCFSearch[#,3]//Timing}]&/@Take[lcf,43]

Length 3 exhaustive

LCFSearchExhaustive[g0_,3]:=Module[{v,g,i1,i2,i3,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[CubicQ[l=LCFNotation[{i1,i2,i3},v/3]]&&c===CanonicalForm[l],Return[LCFMinimal[{i1,i2,i3},v/3]]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]},
{i3,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i2,i3}}]
]

lcf=Last/@Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData["LCF"],("LCF"/.GraphData[#,"NotationRules"])===Missing["NotAvailable"]&&Mod[GraphData[#,"VertexCount"],3]==0&]]

Print[{#,LCFSearchExhaustive[#,3]//Timing}]&/@lcf

Print[{#,LCFSearchExhaustive[#,3]//Timing}]&/@Drop[lcf,13]

Length 4

lcf=Select[GraphData["LCF"],Mod[GraphData[#,"VertexCount"],4]==0&];

Cases[lcf,{"Cage",_}]

Print[{#,LCFSearch[#,4]//Timing}]&/@Cases[lcf,{"Cage",_}]

Print[{#,LCFMinimal@@LCFSearch[#,4]//Timing}]&/@lcf

Length 4 exhaustive

[i, -i, j, -j]

LCFSearchExhaustive[g0_,4]:=Module[{v,g,i1,i2,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&CubicQ[l=LCFNotation[{i1,-i1,i2,-i2},v/4]]&&c===CanonicalForm[l],Return[LCFMinimal[{i1,-i1,i2,-i2},v/4]]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,-i1,i2,-i2}}]
]

lcf=Last/@Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData["LCF"],("LCF"/.GraphData[#,"NotationRules"])===Missing["NotAvailable"]&&Mod[GraphData[#,"VertexCount"],4]==0&]]

Print[{#,LCFSearchExhaustive[#,4]//Timing}]&/@lcf

[i, j, -j, -i]

LCFSearchExhaustive[g0_,4]:=Module[{v,g,i1,i2,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&CubicQ[l=LCFNotation[{i1,i2,-i2,-i1},v/4]]&&c===CanonicalForm[l],Return[LCFMinimal[{i1,i2,-i2,-i1},v/4]]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i2,-i2,i1}}]
]

Print[{#,LCFSearchExhaustive[#,4]//Timing}]&/@lcf

[i, i, j, -j]

LCFSearchExhaustive[g0_,4]:=Module[{v,g,i1,i2,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&CubicQ[l=LCFNotation[{i1,i1,i2,-i2},v/4]]&&c===CanonicalForm[l],Return[LCFMinimal[{i1,i1,i2,-i2},v/4]]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,i1,i2,-i2}}]
]

Print[{#,LCFSearchExhaustive[#,4]//Timing}]&/@lcf

[i, -i, j, j]

LCFSearchExhaustive[g0_,4]:=Module[{v,g,i1,i2,c,l},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Monitor[Do[
If[Abs[i2]>1&&CubicQ[l=LCFNotation[{i1,-i1,i2,i2},v/4]]&&c===CanonicalForm[l],Return[LCFMinimal[{i1,-i1,i2,i2},v/4]]],
{i1,-Floor[v/2],-2},
{i2,-Floor[v/2],Floor[v/2]}
],
{g0,{i1,-i1,i2,i2}}]
]

Print[{#,LCFSearchExhaustive[#,4]//Timing}]&/@lcf

Length 5

lcf=Select[GraphData["LCF"],Mod[GraphData[#,"VertexCount"],5]==0&];

Print[{#,LCFSearch[#,5]//Timing}]&/@Cases[lcf,{"Cage",_}]

Print[{#,LCFSearch[#,5]//Timing}]&/@{{"GeneralizedPetersen",{15,4}},{"Prism",5},{"MoebiusLadder",5}}

Print[{#,LCFSearch[#,5]//Timing}]&/@lcf

Length 6

Print[{#,LCFSearch[#,6]//Timing}]&/@Cases[lcf,{"Cage",_}]

[i,j,k,-i,-j,-k]

"LCF"/.GraphData["Tutte12Cage","NotationRules"]

lcf=Last/@Sort[GraphData[#,{"VertexCount","StandardName"}]&/@Select[GraphData["LCF"],Head["LCF"/.GraphData[#,"NotationRules"]]===Missing&&Mod[GraphData[#,"VertexCount"],6]==0&]]

Print[{#,LCFSearch[#,6]//Timing}]&/@{{"CubicTransitive",20},"Foster024A","Foster048A"}

LCFSearch[{"CubicTransitive",37},6]

Print[{#,LCFSearch[#,6]//Timing}]&/@lcf

Print[{#,LCFSearch[#,6]//Timing}]&/@lcf

Print[{#,LCFSearch[#,6]//Timing}]&/@Drop[lcf,10]

[...]

LCFSearch[g0_,6]:=Module[{v,g,c},
g=CombinatoricaGraph[g0];
c=CanonicalForm[g];
v=V[g];
Union[LCFMinimal6/@Union[Flatten[Table[perms,{i,2,v/2},{j,2,v/2},{k,2,v/2}],2]]]
]

LCF from Embedding

LCFEmbeddingQ[g_Graph]:=Module[{v=N[Vertices[g]],rim},
FreeQ[v,{0,0}|{0.,0.}]&&Chop[Norm[Total[v]]]==0&&Length[Union[Round[10^3Norm/@v]]]==1&&Intersection[Edges[g],rim=Sort[Sort/@Partition[Ordering[Mod[ArcTan@@@v,2π]],2,1,1]]]==rim
]

LCFFromEmbedding[g_]:=Module[{v=N[Vertices[g]],n,lcf,min,c},
n=Length[v];
c=Complement[Sort/@(Edges[g]/.Thread[Ordering[Mod[ArcTan@@@v,2π]]->Range[n]]),Sort/@Partition[Range[n],2,1,1]];
lcf=Sort/@Mod[MapIndexed[Flatten[#2[[1]]-Position[#1,1]]&,ToAdjacencyMatrix[FromUnorderedPairs[c]]]-1,n,-n/2]+1;
min=Select[Table[Take[lcf,#],{n/#}]&/@Divisors[n],Join@@#==lcf&,1];
LCFMinimal[min[[1,1]],n/Length[min[[1,1]]]]
]

{"Antiprism", 4}

ShowGraph/@(gs=GraphData[{"Antiprism",4},"Graphs"])

(lcf=LCFFromEmbedding/@GraphData[{"Antiprism",4},"Graphs","LCF"])//Column

lcf[[All,-1]]

GetGraphData[{"Antiprism",4},"LCF"]//Column

LCFMinimal@@{{{-3,-2},{2,4},{-2,2},{-3,3},{-2,2},{-2,4},{2,3},{-2,2}},1}

{"Andrasfai", 4}

ShowGraph/@(gs=GraphData[{"Andrasfai",4},"Graphs"])

(lcf=LCFFromEmbedding/@GraphData[{"Andrasfai",4},"Graphs","LCF"])//Column

lcf[[All,-1]]

GetGraphData[{"Andrasfai",4},"LCF"]//Column