Iofinova-Ivanov Graphs

Author

Eric W. Weisstein
May 9, 2024

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/Iofinova-IvanovGraphs.nb.

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

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

Enumeration

Select[GraphData[All],!FreeQ[GraphData[#,"StandardNames"],"IofinovaIvanov"]&]

Select[GraphData[All],!FreeQ[GraphData[#,"StandardNames"],"IofinovaIvanovGraph"]&]

Embeddings

<<MathWorld`Graphs`

{"IofinovaIvanov", 110}

Names

GraphData[{"IofinovaIvanov",110},"StandardName"]

GraphData[{"IofinovaIvanov",110},"StandardNames"]

Primary

GraphData[{"IofinovaIvanov",110}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"IofinovaIvanov",110},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"IofinovaIvanov",110},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"IofinovaIvanov",110},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"IofinovaIvanov",110},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"IofinovaIvanov",110},"Graph","Degenerate"]

Configuration

GraphData[{"IofinovaIvanov",110},"Configuration"]

GraphData[{"IofinovaIvanov",110},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"IofinovaIvanov",110},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"IofinovaIvanov",110},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"IofinovaIvanov",110},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"IofinovaIvanov",110},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"IofinovaIvanov",110},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"IofinovaIvanov",110},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"IofinovaIvanov",110},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"IofinovaIvanov",110},"Planar"]

GraphData[{"IofinovaIvanov",110},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"IofinovaIvanov",110},{"RCN","CN"}]

GraphData[{"IofinovaIvanov",110},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"IofinovaIvanov",110}],TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IofinovaIvanov",110}],TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IofinovaIvanov",110}],TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"IofinovaIvanov",110}],TimeConstraint->86400])//AbsoluteTiming

(g=MinimalCrossingGraph[GraphData[{"IofinovaIvanov",110}],"CrossingNumber"->cn])//PolyhedralGraphQ

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"IofinovaIvanov",110}],"CrossingNumber"->cn,RandomSeed->n]],{n,50}],Max[OuterFace[#]]<=GraphData[{"IofinovaIvanov",110},"V"]&]]//Timing

Table[MinimalCrossingGraph[GraphData[{"IofinovaIvanov",110}],"CrossingNumber"->cn,RandomSeed->i],{i,50}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"IofinovaIvanov",110},"Circulant"]

GraphData[{"IofinovaIvanov",110},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"IofinovaIvanov",110},"ComplementGraph","Name"]

Line graph

GraphData[{"IofinovaIvanov",110},"Line"]

LineGraphQ[GraphData[{"IofinovaIvanov",110}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"IofinovaIvanov",110}&]

RootGraph[GraphData[{"IofinovaIvanov",110}]]

Halin

GraphData[{"IofinovaIvanov",110},"Halin"]

GraphData[{"IofinovaIvanov",110},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"IofinovaIvanov",110},"Rigid"]

GraphData[{"IofinovaIvanov",110},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"IofinovaIvanov",110},"Flexible"]

GraphData[{"IofinovaIvanov",110},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"IofinovaIvanov",110},"LCF"]

GraphData[{"IofinovaIvanov",110},"HamiltonianCycleCount"]

GraphData[{"IofinovaIvanov",110},"LCFSignature"]

GraphData[{"IofinovaIvanov",110},"LCFNotations"]

GraphData[{"IofinovaIvanov",110},"Graph","LCF"]//StyleGraphs

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

LCF compute all

Divisors[GraphData[{"IofinovaIvanov",110},"V"]]

Length[FindHamiltonianCycle[GraphData[{"IofinovaIvanov",110}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

Tally[(lcf=ReadProperty["LCFNotations",GraphNameToFileName[{"IofinovaIvanov",110},".m.gz"]])[[All,2]]]//Timing

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"IofinovaIvanov",110},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"IofinovaIvanov",110}],Debug->True]//Timing

GraphData[{"IofinovaIvanov",110},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"IofinovaIvanov",110},"VertexList"],GraphData[{"IofinovaIvanov",110},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

FindUnitDistanceEmbedding[GraphData[{"IofinovaIvanov",110}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData[{"IofinovaIvanov",110},"Matchstick"]

GraphData[{"IofinovaIvanov",110},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"IofinovaIvanov",110},"Edges"]]

3D All

GraphData[{"IofinovaIvanov",110},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"IofinovaIvanov",110},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"IofinovaIvanov",110},"Polyhedral"]

GraphData[{"IofinovaIvanov",110},"Graph",{"3D","Polyhedron"}]

Construction

Length[v={{294.5,512.5},{345.5,509.5},{393.5,497.5},{455.5,455.5},{498.5,392.5},{513.5,345.5},{491.5,220.5},{406.5,134.5},{280.5,114.5},{171.5,172.5},{115.5,281.5},{133.5,406.5},{220.5,491.5},{357.5,591.5},{411.5,609.5},{495.5,564.5},{511.5,511.5},{566.5,492.5},{610.5,408.5},{591.5,355.5},{616.5,313.5},{513.5,294.5},{608.5,214.5},{562.5,184.5},{563.5,129.5},{446.5,159.5},{497.5,61.5},{438.5,64.5},{411.5,16.5},{355.5,118.5},{314.5,7.5},{268.5,36.5},{215.5,15.5},{211.5,138.5},{130.5,59.5},{113.5,115.5},{61.5,132.5},{139.5,211.5},{16.5,217.5},{36.5,269.5},{9.5,311.5},{16.5,406.5},{64.5,438.5},{61.5,494.5},{130.5,565.5},{184.5,564.5},{218.5,604.5},{162.5,444.5},{114.5,357.5},{377.5,190.5},{427.5,254.5},{450.5,334.5},{402.5,403.5},{333.5,450.5},{254.5,427.5},{187.5,291.5},{214.5,215.5},{293.5,186.5},{364.5,211.5},{427.5,328.5},{330.5,427.5},{209.5,365.5},{189.5,375.5},{431.5,304.5},{420.5,266.5},{409.5,263.5},{411.5,252.5},{388.5,220.5},{343.5,199.5},{302.5,195.5},{295.5,204.5},{287.5,199.5},{248.5,214.5},{232.5,230.5},{214.5,248.5},{198.5,342.5},{205.5,295.5},{195.5,301.5},{200.5,285.5},{223.5,386.5},{306.5,429.5},{267.5,420.5},{263.5,409.5},{253.5,412.5},{356.5,422.5},{423.5,354.5},{401.5,388.5},{389.5,389.5},{389.5,402.5},{326.5,396.5},{343.5,343.5},{397.5,324.5},{353.5,291.5},{354.5,233.5},{304.5,267.5},{250.5,249.5},{271.5,305.5},{235.5,351.5},{292.5,352.5},{316.5,334.5},{336.5,315.5},{325.5,294.5},{297.5,296.5},{291.5,322.5},{313.5,617.5}}]

v2={{365.5,210.5},{426.5,330.5},{330.5,426.5},{210.5,365.5},{231.5,230.5}};

dup=Flatten[Nearest[Thread[v->Range[105]],#,1]&/@v2]

doub=With[{θ=4Degree,o=Mean[v]},{(o+RotationMatrix[-θ].(#-o))&/@v2,(o+RotationMatrix[θ].(#-o))&/@v2}]

doub=With[{s=.04,o=Mean[v]},{(o+(1-s)(#-o))&/@v2,(o+(1+s)(#-o))&/@v2}]

Length[newv=Join[Delete[v,List/@dup],Sequence@@doub]]

Graphics[Point[newv]]

tt[x_]:={{x,x+1},{x+1,x+2}}

ShowLabeledGraph[g=Graph[List/@
Join[{{100,14},{14,15}},
Flatten[tt/@{16,19,23,27,31,35,39,42,45},1],
{{4,17},{6,20},{7,24},{8,28},{9,32},{10,36},{11,40},{12,43},{13,46},{2,14},{2,4},{4,6},{6,7},{7,8},{8,9},{9,10},{10,11},{11,12},{12,13},{13,2},{15,52},{52,27},{100,59},{59,37},{33,34},{34,56},{56,48},{48,45},{35,50},{50,21},{39,38},{38,58},{58,26},{26,25},{47,1},{1,53},{53,22},{22,23},{44,54},{54,19},{18,5},{5,51},{51,30},{30,31},{41,49},{49,55},{55,3},{3,16},{42,57},{57,29},{100,76},{76,66},{66,31},{42,71},{71,61},{61,23},{44,75},{75,63},{63,25},{21,60},{60,73},{73,41},{37,70},{70,82},{82,18},{39,74},{74,81},{81,19},{35,69},{69,84},{84,16},{33,68},{68,80},{80,15},{93,94},{94,85},{85,86},{86,87},{87,88},{88,89},{89,90},{90,91},{91,92},{92,93},{29,65},{65,77},{77,47},{45,79},{79,64},{64,27},{95,90},{88,99},{96,92},{94,97},{98,86},{69,67},{67,65},{67,58},{70,72},{72,71},{75,78},{78,76},{80,83},{83,81},{64,62},{62,60},{56,72},{51,62},{83,53},{55,78}}
],List/@newv],VertexStyle->Disk[.01],EdgeStyle->AbsoluteThickness[1],ImageSize->600]

r={104,103,102,101,105};
R=r+5;
p={93,85,87,89,91};
lt={73,77,82,63,68};
rt={74,79,84,61,66};
Lt={75,80,60,65,70};
Rt={71,76,81,64,69};
llt={48,3,22,30,38};
rrt={49,1,5,26,34};
ρ={59,54,52,50,57};
i={99,95,96,97,98};

{llt,R|r},{rrt,R|r},{lt,RotateRight[r|R]},{rt,R|r},{i,RotateLeft[r|R]},{i,RotateRight[r|R]}

2^6

rs={R,r};

e=Flatten[Transpose/@{{p,ρ}},1]

t=Flatten[#,1]&/@Flatten[Table[Transpose/@{{llt,rs[[k1]]},{rrt,rs[[k2]]},{lt,RotateRight[rs[[k3]]]},{rt,rs[[k4]]},{i,RotateLeft[rs[[k5]]]},{i,RotateRight[rs[[k6]]]}},{k1,2},{k2,2},{k3,2},{k4,2},{k5,2},{k6,2}],5];

cubic=Select[AddEdges[AddEdges[g,{{93,59},{85,54},{87,52},{89,50},{91,57}}],#]&/@t,CubicQ]

ss=Select[cubic,EdgeTransitiveQ]

GraphPlot[#,Method->None,ImageSize->500]&/@ss

FastIsomorphicQ@@ss

s110=First[ss]

SemisymmetricQ[s110]

CubicQ[s110]

emb=GraphData[{"IofinovaIvanov",110},"Embeddings"];

{emb[[1]]/500,ToCommonEdges[ss[[2]],Graph[{"IofinovaIvanov",110}]]/500,emb[[-1]]}//PadVertices

GraphData

GraphClassString

GraphClassString[{"IofinovaIvanov",110}]

GraphDataString

file=OpenWrite["s110.m"]

WriteString[file,GraphDataString[s110,
"StandardName"->{"IofinovaIvanov",110},
"Name"->"Ivanov-Iofinova graph",
"Information"->"CubicSemisymmetricGraph",
"Vertices"->Vertices/@ss,
Debug->True,
TimeConstraint->120
]]

Close[file]