Cameron Graph

Author

Eric W. Weisstein
October 3, 2025

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["CameronGraph","StandardName"]

GraphData["CameronGraph","StandardNames"]

Primary

GraphData["CameronGraph"]//StyleGraphs[#,VertexSize->1,ImageSize->Medium,EdgeStyle->Directive[LightDarkSwitched@Black,AbsoluteThickness[.05]]]&

All

GraphData["CameronGraph","Graph","All"]//StyleGraphs[#,VertexSize->1,EdgeStyle->Directive[LightDarkSwitched@Black,AbsoluteThickness[.05]]]&

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["CameronGraph"]]

Default embedding

GraphPlot[Graph[GraphData["CameronGraph","VertexList"],GraphData["CameronGraph","Edges"]]]

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData["CameronGraph","Graph","Degenerate"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

GeneralizedPetersen

GraphData["CameronGraph","Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

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

Bilateral

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

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

Circular

GraphData["CameronGraph","Graph","Circular"]//StyleGraphs[#,VertexSize->1,EdgeStyle->Directive[LightDarkSwitched@Black,AbsoluteThickness[.05]]]&

Circular construction

GraphData["CameronGraph","Hamiltonian"]

GraphData["CameronGraph","LCF"]

GraphData["CameronGraph","HamiltonianCycleCount"]

Planar

GraphData["CameronGraph","Planar"]

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossingNumber crossings.uos.de

https://crossings.uos.de/job/new

ExportString[GraphData["CameronGraph"],"DOT"]

MinimalCrossing

GraphData["CameronGraph","CN"]

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

MinimalRectilinearCrossing

GraphData["CameronGraph","RCN"]

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

MinimalCrossing construction

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

Tutte:

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

TutteGraphs=BilateralGraph[CenterGraph@IGLayoutTutte[g,"OuterFace"->#],"ReturnNonbilateralGraph"->True]&/@faces

TutteGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["CameronGraph","V"]])]
}&/@TutteGraphs;

Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Select[Cases[TutteGraphsWithOuterCrossingPointCounts,{g_,1}:>g],Length[OuterFace[#]]>3&]

TutteGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["CameronGraph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@TutteGraphs;

DeleteCases[
TutteGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]

Random:

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["CameronGraph","V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,0}:>g]

Select[Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g],Length[OuterFace[#]]>3&]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData["CameronGraph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

DeleteCases[
RandomGraphsWithSymmetryGroups,
{_,TransformationGroup[{}]}
]/.g_Graph:>BilateralGraph[CenterGraph@g,"ReturnNonbilateralGraph"->True]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

GraphData["CameronGraph","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["CameronGraph"],TimeConstraint->10])//AbsoluteTiming

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

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

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

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

Circulant

GraphData["CameronGraph","Circulant"]

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

Circulant construction

GraphData["CameronGraph","NotationRules","Circulant"]

(ci=CirculantIndices[GraphData["CameronGraph"]])//Timing

CirculantGraph1@@@ci

Cases[GraphData["CameronGraph","StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData["CameronGraph","ComplementGraph","Name"]

Line graph

GraphData["CameronGraph","Line"]

LineGraphQ[GraphData["CameronGraph"]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==="CameronGraph"&]

RootGraph[GraphData["CameronGraph"]]

Halin

GraphData["CameronGraph","Halin"]

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

Rigid

GraphData["CameronGraph","Rigid"]

GraphData["CameronGraph","Graph","Rigid"]//StyleGraphs

Flexible

GraphData["CameronGraph","Flexible"]

GraphData["CameronGraph","Graph","Flexible"]//StyleGraphs

LCF

GraphData["CameronGraph","LCF"]

GraphData["CameronGraph","HamiltonianCycleCount"]

GraphData["CameronGraph","LCFSignature"]

GraphData["CameronGraph","LCFNotations"]

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

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

LCF compute random

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

FindRandomLCFNotation[GraphData["CameronGraph"],TimeConstraint->3600]

LCF compute 10^2 [0.3 GB]

Tally[(lcf=LCF[GraphData["CameronGraph"],10^2])[[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

LCF compute 10^4 [0.8 GB]

Tally[(lcf=LCF[GraphData["CameronGraph"],10^4])[[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

LCF compute 10^5 [5.8 GB]

Tally[(lcf=LCF[GraphData["CameronGraph"],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

MaxMemoryUsed[]/10.^9 "GB"

Length[gs]

gs

BilateralGraphEmbeddingQ/@gs

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData["CameronGraph"],10^6])[[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

LCF compute all

Divisors[GraphData["CameronGraph","V"]]

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

Tally[(lcf=LCF[GraphData["CameronGraph"],All])[[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

UnitDistance

GraphData["CameronGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["CameronGraph","VertexList"],GraphData["CameronGraph","EdgeList"]],MaxIterations->500]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData["CameronGraph"],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

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

Matchstick

GraphData["CameronGraph","Matchstick"]

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

3D default

Graph3D[GraphData["CameronGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["CameronGraph","Polyhedral"]

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

Construction

distanceregular.org

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

VertexCount[g]

GraphDiameter[g]//Timing

RegularParameters[g]//Timing

DistanceRegularGraphQ[g]//Timing

IntersectionArray[g]//Timing

IntegerSpectrum[g]//SpectrumForm

GroupOrder[GraphAutomorphismGroup[g]]

HamiltonianGraphQ[g]

GraphData

GraphDataClassString

GraphDataClassString["CameronGraph"]

GraphDataString

VertexCount[g]

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

WriteString[file,GraphDataString[g,
"StandardName"->"CameronGraph",
"Name"->"Cameron graph",
"Embeddings"->None,
"Information"->"CameronGraph",
"Classes"->{"DistanceRegular","Noncirculant","Nongrid"},
Debug->True,
TimeConstraint->10]]

Close[file]