van Lint-Schrijver Graph

Author

Eric W. Weisstein
July 25, 2025

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/vanLint-SchrijverGraph.nb.

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

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

Figure

GraphicsGrid[Partition[GraphData["VanLintSchrijverGraph","Graph","All"]//StyleGraphs[#,VertexSize->{"Scaled",.015},EdgeStyle->Directive[LightDarkSwitched@Black,Thin]]&,UpTo[5]],Dividers->All]

Embeddings

<<MathWorld`Graphs`

Names

GraphData["VanLintSchrijverGraph","StandardName"]

GraphData["VanLintSchrijverGraph","StandardNames"]

Primary

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

All

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

Default embedding

GraphPlot@GraphData["VanLintSchrijverGraph","Edges"]

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

RecognizeGraph[g]

Embedding types

GraphDataEmbeddings[GraphData["VanLintSchrijverGraph","EdgeList"]]

Degenerate

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

HouseOfGraphs

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

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

IGraph

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

Bilateral

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

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

Circular

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

Circular construction

GraphData["VanLintSchrijverGraph","Hamiltonian"]

GraphData["VanLintSchrijverGraph","LCF"]

GraphData["VanLintSchrijverGraph","HamiltonianCycleCount"]

Planar

GraphData["VanLintSchrijverGraph","Planar"]

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossing

GraphData["VanLintSchrijverGraph","CN"]

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

MinimalRectilinearCrossing

GraphData["VanLintSchrijverGraph","RCN"]

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

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["VanLintSchrijverGraph"],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["VanLintSchrijverGraph"],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

GraphData["VanLintSchrijverGraph","Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

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

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

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

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

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

Circulant

GraphData["VanLintSchrijverGraph","Circulant"]

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

Halin

GraphData["VanLintSchrijverGraph","Halin"]

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

LCF

Divisors[GraphData["VanLintSchrijverGraph","V"]]

GraphData["VanLintSchrijverGraph","LCF"]

GraphData["VanLintSchrijverGraph","LCFSignature"]

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

GraphData["VanLintSchrijverGraph","LCFNotations"]

LCF compute random

FindRandomLCFNotation[GraphData["VanLintSchrijverGraph"],TimeConstraint->120]

LCF compute 10^3 [0.3 GB]

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

LCF compute 10^4 [0.4 GB]

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

DeleteCases[BilateralLCFGraph[#,"NonbilateralValue"->"Missing"]&/@%,_Missing]

GraphSymmetryGroup/@%

LCF compute 10^5 [1.5 GB]

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

DeleteCases[BilateralLCFGraph[#,"NonbilateralValue"->"Missing"]&/@%,_Missing]

GraphSymmetryGroup/@%

LCF compute 10^6 [12.7 GB]

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

DeleteCases[BilateralLCFGraph[#,"NonbilateralValue"->"Missing"]&/@%,_Missing]

GraphSymmetryGroup/@%

LCF compute 10^7 [119.7 GB]

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

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

DeleteCases[BilateralLCFGraph[#,"NonbilateralValue"->"Missing"]&/@%,_Missing]

GraphSymmetryGroup/@%

Length[%6]

LCF compute all

Length[FindHamiltonianCycle[GraphData["VanLintSchrijverGraph"],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData["VanLintSchrijverGraph"],All])[[All,2]]]

gs=LCFGraph@@@DeleteCases[lcf,{_,1|2}]

UnitDistance

GraphData["VanLintSchrijverGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine/@GraphData["VanLintSchrijverGraph","Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData["VanLintSchrijverGraph","Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["VanLintSchrijverGraph"],MaxIterations->1000,"ReturnWithMessage"->True]//Timing

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

FindUnitDistanceEmbedding[GraphData["VanLintSchrijverGraph"],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

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

Matchstick

GraphData["VanLintSchrijverGraph","Matchstick"]

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

3D default

Graph3D[GraphData["VanLintSchrijverGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["VanLintSchrijverGraph","Polyhedral"]

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

Construction

distanceregular.org

g=DistanceRegularGraph["http://www.distanceregular.org/graphdata/vls.am"]

RecognizeGraph[g]

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

GraphData

GraphDataString

VertexCount[g]

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

WriteString[file,GraphDataString[g,
"StandardName"->"VanLintSchrijverGraph",
"Name"->"van Lint-Schrijver graph",
"Embeddings"->None,
"Information"->"vanLint-SchrijverGraph",
"Classes"->{"DistanceRegular","Noncirculant","Nongrid"},
Debug->True,
TimeConstraint->10]];

Close[file]