Pasechnik Graph

Author

Eric W. Weisstein
May 7, 2024

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

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

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

Source

Pasechnik, D. V.  "Skew-symmetric association schemes with two classes and strongly regular graphs of type (Subscript[L, 2n-1])(4n-1)."  Acta Applicandaie Math. 29, 129–138, 1992. doi:10.1007/BF00053382.

Graphs

GraphicsRow[DeleteCases[Show[StyleGraphs@GraphData[#],PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Black,Opacity[1],Italic,FontFamily->"Times",12]]&/@With[{class="Pasechnik"},Sort[{GraphData[#,"NotationRules",class],#}&/@GraphData[class]][[All,2]]],_Show]]

Special cases

With[{class="Pasechnik"},TextGrid[Sort[{Lookup[GraphData[#,"NotationRules"],class],GraphData[#,"V"],#}&/@GraphData[class]],Dividers->All,Alignment->{{Left,Decimal,Left}}]]

Embeddings

<<MathWorld`Graphs`

{"Pasechnik", 1} == "3C3"

Names

GraphData[{"Pasechnik",1},"StandardName"]

GraphData[{"Pasechnik",1},"StandardNames"]

{"Pasechnik", 2}

Names

GraphData[{"Pasechnik",2},"StandardName"]

GraphData[{"Pasechnik",2},"StandardNames"]

Primary

GraphData[{"Pasechnik",2}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Pasechnik",2},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Pasechnik",2},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Pasechnik",2},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Pasechnik",2},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Pasechnik",2},"Graph","Degenerate"]

Configuration

GraphData[{"Pasechnik",2},"Configuration"]

GraphData[{"Pasechnik",2},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Pasechnik",2},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Pasechnik",2},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"Pasechnik",2},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"Pasechnik",2},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Pasechnik",2},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Pasechnik",2},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Pasechnik",2},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Pasechnik",2},"Planar"]

GraphData[{"Pasechnik",2},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Pasechnik",2},{"RCN","CN"}]

GraphData[{"Pasechnik",2},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Pasechnik",2}],"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[{"Pasechnik",2},"Circulant"]

GraphData[{"Pasechnik",2},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Pasechnik",2},"ComplementGraph","Name"]

Line graph

GraphData[{"Pasechnik",2},"Line"]

LineGraphQ[GraphData[{"Pasechnik",2}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Pasechnik",2}&]

RootGraph[GraphData[{"Pasechnik",2}]]

Halin

GraphData[{"Pasechnik",2},"Halin"]

GraphData[{"Pasechnik",2},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Pasechnik",2},"Rigid"]

GraphData[{"Pasechnik",2},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Pasechnik",2},"Flexible"]

GraphData[{"Pasechnik",2},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Pasechnik",2},"LCF"]

GraphData[{"Pasechnik",2},"HamiltonianCycleCount"]

GraphData[{"Pasechnik",2},"LCFSignature"]

GraphData[{"Pasechnik",2},"LCFNotations"]

GraphData[{"Pasechnik",2},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Pasechnik",2}],TimeConstraint->120]

LCF compute 10^3

Tally[(lcf=LCF[GraphData[{"Pasechnik",2}],10^3])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^4

Tally[(lcf=LCF[GraphData[{"Pasechnik",2}],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Pasechnik",2}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Pasechnik",2}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Pasechnik",2}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Pasechnik",2},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Pasechnik",2},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Pasechnik",2}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Pasechnik",2},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Pasechnik",2}],Debug->True]//Timing

GraphData[{"Pasechnik",2},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Pasechnik",2},"VertexList"],GraphData[{"Pasechnik",2},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Pasechnik",2},"Matchstick"]

GraphData[{"Pasechnik",2},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Pasechnik",2},"Edges"]]

3D All

GraphData[{"Pasechnik",2},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Pasechnik",2},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Pasechnik",2},"Polyhedral"]

GraphData[{"Pasechnik",2},"Graph",{"3D","Polyhedron"}]

{"Pasechnik", 3}

Names

GraphData[{"Pasechnik",3},"StandardName"]

GraphData[{"Pasechnik",3},"StandardNames"]

Primary

GraphData[{"Pasechnik",3}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Pasechnik",3},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Pasechnik",3},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Pasechnik",3},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Pasechnik",3},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Pasechnik",3},"Graph","Degenerate"]

Configuration

GraphData[{"Pasechnik",3},"Configuration"]

GraphData[{"Pasechnik",3},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Pasechnik",3},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Pasechnik",3},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"Pasechnik",3},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"Pasechnik",3},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Pasechnik",3},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Pasechnik",3},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Pasechnik",3},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Pasechnik",3},"Planar"]

GraphData[{"Pasechnik",3},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Pasechnik",3},{"RCN","CN"}]

GraphData[{"Pasechnik",3},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Pasechnik",3}],"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[{"Pasechnik",3},"Circulant"]

GraphData[{"Pasechnik",3},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Pasechnik",3},"ComplementGraph","Name"]

Line graph

GraphData[{"Pasechnik",3},"Line"]

LineGraphQ[GraphData[{"Pasechnik",3}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Pasechnik",3}&]

RootGraph[GraphData[{"Pasechnik",3}]]

Halin

GraphData[{"Pasechnik",3},"Halin"]

GraphData[{"Pasechnik",3},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Pasechnik",3},"Rigid"]

GraphData[{"Pasechnik",3},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Pasechnik",3},"Flexible"]

GraphData[{"Pasechnik",3},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Pasechnik",3},"LCF"]

GraphData[{"Pasechnik",3},"HamiltonianCycleCount"]

GraphData[{"Pasechnik",3},"LCFSignature"]

GraphData[{"Pasechnik",3},"LCFNotations"]

GraphData[{"Pasechnik",3},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Pasechnik",3}],TimeConstraint->120]

LCF compute 10^4

Tally[(lcf=LCF[GraphData[{"Pasechnik",3}],10^4])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Pasechnik",3}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^6

Tally[(lcf=LCF[GraphData[{"Pasechnik",3}],10^6])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

LCF compute 10^7

Tally[(lcf=LCF[GraphData[{"Pasechnik",3}],10^7])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Pasechnik",3},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Pasechnik",3},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Pasechnik",3}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Pasechnik",3},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Pasechnik",3}],Debug->True]//Timing

GraphData[{"Pasechnik",3},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Pasechnik",3},"VertexList"],GraphData[{"Pasechnik",3},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Pasechnik",3},"Matchstick"]

GraphData[{"Pasechnik",3},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Pasechnik",3},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Pasechnik",3},"Polyhedral"]

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

{"Pasechnik", 4}

Names

GraphData[{"Pasechnik",4},"StandardName"]

GraphData[{"Pasechnik",4},"StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Pasechnik",4},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Pasechnik",4},"Edges"]

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

RecognizeGraph[g]

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData[{"Pasechnik",4},"Graph","Degenerate"]

Configuration

GraphData[{"Pasechnik",4},"Configuration"]

GraphData[{"Pasechnik",4},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Pasechnik",4},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Pasechnik",4},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"Pasechnik",4},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"Pasechnik",4},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Pasechnik",4},"Graph","IGraph"]//StyleGraphs

Bilateral

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

Circular

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

Planar

GraphData[{"Pasechnik",4},"Planar"]

GraphData[{"Pasechnik",4},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Pasechnik",4},{"RCN","CN"}]

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

MinimalCrossing construction

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

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

(cn=CrossingNumber[GraphData[{"Pasechnik",4}],TimeConstraint->60])//AbsoluteTimingPSC-GOL

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Pasechnik",4}],"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[{"Pasechnik",4},"Circulant"]

GraphData[{"Pasechnik",4},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Pasechnik",4},"ComplementGraph","Name"]

Line graph

GraphData[{"Pasechnik",4},"Line"]

LineGraphQ[GraphData[{"Pasechnik",4}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Pasechnik",4}&]

RootGraph[GraphData[{"Pasechnik",4}]]

Halin

GraphData[{"Pasechnik",4},"Halin"]

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

Rigid

GraphData[{"Pasechnik",4},"Rigid"]

GraphData[{"Pasechnik",4},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Pasechnik",4},"Flexible"]

GraphData[{"Pasechnik",4},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Pasechnik",4},"LCF"]

GraphData[{"Pasechnik",4},"HamiltonianCycleCount"]

GraphData[{"Pasechnik",4},"LCFSignature"]

GraphData[{"Pasechnik",4},"LCFNotations"]

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

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Pasechnik",4}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Pasechnik",4}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Pasechnik",4},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Pasechnik",4},"V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Pasechnik",4},"UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Pasechnik",4},"VertexList"],GraphData[{"Pasechnik",4},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Pasechnik",4},"Matchstick"]

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

3D default

Graph3D[GraphData[{"Pasechnik",4},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Pasechnik",4},"Polyhedral"]

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

{"Pasechnik", 5}

Names

GraphData[{"Pasechnik",5},"StandardName"]

GraphData[{"Pasechnik",5},"StandardNames"]

Primary

GraphData[{"Pasechnik",5}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Pasechnik",5},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Pasechnik",5},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Pasechnik",5},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Pasechnik",5},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"Pasechnik",5},"Graph","Degenerate"]

Configuration

GraphData[{"Pasechnik",5},"Configuration"]

GraphData[{"Pasechnik",5},"Graph","Configuration"]//StyleGraphs

Perspective

GraphData[{"Pasechnik",5},"Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData[{"Pasechnik",5},"Polyhedron"]

HoneycombToroidal construction

GraphData[{"Pasechnik",5},"NotationRules","HoneycombToroidal"]

GeneralizedPetersen

GraphData[{"Pasechnik",5},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"Pasechnik",5},"Graph","IGraph"]//StyleGraphs

Bilateral

GraphData[{"Pasechnik",5},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Pasechnik",5},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Pasechnik",5},"Planar"]

GraphData[{"Pasechnik",5},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Pasechnik",5},{"RCN","CN"}]

GraphData[{"Pasechnik",5},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData[{"Pasechnik",5}],"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[{"Pasechnik",5},"Circulant"]

GraphData[{"Pasechnik",5},"Graph","Circulant"]//StyleGraphs

Complement graph

compl=GraphData[{"Pasechnik",5},"ComplementGraph","Name"]

Line graph

GraphData[{"Pasechnik",5},"Line"]

LineGraphQ[GraphData[{"Pasechnik",5}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]=== {"Pasechnik",5}&]

RootGraph[GraphData[{"Pasechnik",5}]]

Halin

GraphData[{"Pasechnik",5},"Halin"]

GraphData[{"Pasechnik",5},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"Pasechnik",5},"Rigid"]

GraphData[{"Pasechnik",5},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"Pasechnik",5},"Flexible"]

GraphData[{"Pasechnik",5},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"Pasechnik",5},"LCF"]

GraphData[{"Pasechnik",5},"HamiltonianCycleCount"]

GraphData[{"Pasechnik",5},"LCFSignature"]

GraphData[{"Pasechnik",5},"LCFNotations"]

GraphData[{"Pasechnik",5},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"Pasechnik",5}],TimeConstraint->120]

LCF compute 10^5

Tally[(lcf=LCF[GraphData[{"Pasechnik",5}],10^5])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

l={
{{"Pasechnik",5},{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.1"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData[{"Pasechnik",5},"V"]]

Length[FindHamiltonianCycle[GraphData[{"Pasechnik",5}],All][[All,All,1]]]//Timing

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

UnitDistance

GraphData[{"Pasechnik",5},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Pasechnik",5}],Debug->True]//Timing

GraphData[{"Pasechnik",5},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Pasechnik",5},"VertexList"],GraphData[{"Pasechnik",5},"EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

Matchstick

GraphData[{"Pasechnik",5},"Matchstick"]

GraphData[{"Pasechnik",5},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Pasechnik",5},"Edges"]]

3D All

GraphData[{"Pasechnik",5},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Pasechnik",5},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Pasechnik",5},"Polyhedral"]

GraphData[{"Pasechnik",5},"Graph",{"3D","Polyhedron"}]

Properties

VertexCount

Function[{gn,n},{gn,GraphData[gn,"V"],(4n-1)^2}]@@@({#,Sequence@@Lookup[GraphData[#,"NotationRules"],"Pasechnik"]}&/@GraphData["Pasechnik"])

DeleteCases[%,{_,x_,x_}]

Construction

https://doc.sagemath.org/html/en/reference/graphs/sage/graphs/graph_generators.html#sage.graphs.graph_generators.GraphGenerators.PasechnikGraph

Table[(4n-1)^2,{n,7}]

ps=Table[SageGraph[SageEvaluate["graphs.PasechnikGraph("<>ToString[n]<>").edges()"]],{n,6}]

VertexCount/@ps

RecognizeGraph/@ps

RegularParameters/@ps//Column

TextGrid[Table[{(4n-1)^2,2(((2n-1))^2),4n^2-6n+3,2n(2n+1)},{n,5}],Dividers->All,Alignment->Decimal]

GraphData

GraphDataClassString

GraphDataClassString[g]

GraphDataString

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

Do[WriteString[file,GraphDataString[g[i],
"StandardName"->{"Pasechnik",i},
"Name"->ToString[i]<>"\[Hyphen]Pasechnik graph",
"Information"->None,
"NotationRules"->{"Pasechnik"->i},
"Classes"->{"Pasechnik"},
"Embeddings"->{},
"Skip"->{"Arboricity","BurningNumber","Chord","ChordlessCycle","ChordlessCycles","Chords","ChromaticNumber","CliqueCoveringNumber","ComplementOddChordlessCycle","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","CrossingNumber","Cycles","CyclePolynomial","DominatingSet","DominatingSets","EdgeCovers","GracefulLabeling","GracefulLabelings","HamiltonianCycles","HamiltonianPaths","HamiltonianWalks","IdiosyncraticPolynomial","IndependentVertexSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximallyNonhamiltonian","MaximumFlowMatrix","MaximumIndependentEdgeSets","MinimumCoveringsByMaximalCliques","MinimumEdgeColoring","MinimumVertexColoring","MinimumVertexCut","MinimumVertexCuts","MinimumWeightFractionalColoring","MinimumWeightFractionalEdgeColoring","OddChordlessCycles","PathPolynomial","Paths","RadioLabeling","RadioLabelings","RadioNumber","RectilinearCrossingCount","ResistanceMatrix","Skewness","StronglyPerfect","UnitDistance","VertexCover","Thickness"},
TimeConstraint->10
]],{i,2,5}]

Close[file]