Cremona-Richmond Configuration

Author

Eric W. Weisstein
May 22, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/Configurations/Cremona-RichmondConfiguration.nb.

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

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

Source

Boben, M.; Grünbaum, B.; Pisanski, T.; and Zitnik.  "Small Triangle-Free Configurations of Points and Lines."  Disc. Comput. Geom. 35, 405–427, 2006.

https://link.springer.com/content/pdf/10.1007/s00454-005-1224-9.pdf?pdf=button

There is a unique triangle-free (Subscript[15, 3]) configuration, and it is "point "transitive

Figure

pts={{(1/2),(NumericalApproximation[Root, (RowDefault["-0.688", FEExpressionsNumericalApproximationElider]), Root[1-40 ((#1)^2)+80 ((#1)^4)&,1], ])},{(1/4) (1+(Sqrt[5])),(NumericalApproximation[Root, (RowDefault["0.263", FEExpressionsNumericalApproximationElider]), Root[1-20 ((#1)^2)+80 ((#1)^4)&,3], ])},{0,(NumericalApproximation[Root, (RowDefault["0.851", FEExpressionsNumericalApproximationElider]), Root[1-5 ((#1)^2)+5 ((#1)^4)&,4], ])},{(1/4) (-1-(Sqrt[5])),(NumericalApproximation[Root, (RowDefault["0.263", FEExpressionsNumericalApproximationElider]), Root[1-20 ((#1)^2)+80 ((#1)^4)&,3], ])},{-(1/2),(NumericalApproximation[Root, (RowDefault["-0.688", FEExpressionsNumericalApproximationElider]), Root[1-40 ((#1)^2)+80 ((#1)^4)&,1], ])},{(1/2),(NumericalApproximation[Root, (RowDefault["2.39", FEExpressionsNumericalApproximationElider]), Root[361-520 ((#1)^2)+80 ((#1)^4)&,4], ])},{(1/2) (-2-(Sqrt[5])),(NumericalApproximation[Root, (RowDefault["1.21", FEExpressionsNumericalApproximationElider]), Root[121-200 ((#1)^2)+80 ((#1)^4)&,4], ])},{(1/4) (-5-(Sqrt[5])),(NumericalApproximation[Root, (RowDefault["-1.64", FEExpressionsNumericalApproximationElider]), Root[121-260 ((#1)^2)+80 ((#1)^4)&,1], ])},{1,(NumericalApproximation[Root, (RowDefault["-2.23", FEExpressionsNumericalApproximationElider]), Root[1-25 ((#1)^2)+5 ((#1)^4)&,1], ])},{(1/4) (3+3 (Sqrt[5])),(NumericalApproximation[Root, (RowDefault["0.263", FEExpressionsNumericalApproximationElider]), Root[1-20 ((#1)^2)+80 ((#1)^4)&,3], ])},{(NumericalApproximation[Root, (RowDefault["2.27", FEExpressionsNumericalApproximationElider]), Root[-261+1338 #1-1120 ((#1)^2)-144 ((#1)^3)+176 ((#1)^4)&,4], ]),(NumericalApproximation[Root, (RowDefault["0.0420", FEExpressionsNumericalApproximationElider]), Root[81-47340 ((#1)^2)+769760 ((#1)^4)-2579200 ((#1)^6)+774400 ((#1)^8)&,5], ])},{(NumericalApproximation[Root, (RowDefault["0.662", FEExpressionsNumericalApproximationElider]), Root[-9-258 #1+868 ((#1)^2)-808 ((#1)^3)+176 ((#1)^4)&,2], ]),(NumericalApproximation[Root, (RowDefault["2.17", FEExpressionsNumericalApproximationElider]), Root[9801-406980 ((#1)^2)+2964560 ((#1)^4)-4270400 ((#1)^6)+774400 ((#1)^8)&,8], ])},{(NumericalApproximation[Root, (RowDefault["-1.86", FEExpressionsNumericalApproximationElider]), Root[81+648 #1+1368 ((#1)^2)+888 ((#1)^3)+176 ((#1)^4)&,2], ]),(NumericalApproximation[Root, (RowDefault["1.30", FEExpressionsNumericalApproximationElider]), Root[531441-6065280 ((#1)^2)+10115360 ((#1)^4)-5278400 ((#1)^6)+774400 ((#1)^8)&,7], ])},{(NumericalApproximation[Root, (RowDefault["-1.81", FEExpressionsNumericalApproximationElider]), Root[99-258 #1-200 ((#1)^2)+304 ((#1)^3)+176 ((#1)^4)&,1], ]),(NumericalApproximation[Root, (RowDefault["-1.37", FEExpressionsNumericalApproximationElider]), Root[9801-760140 ((#1)^2)+14344160 ((#1)^4)-8883200 ((#1)^6)+774400 ((#1)^8)&,2], ])},{(NumericalApproximation[Root, (RowDefault["0.742", FEExpressionsNumericalApproximationElider]), Root[9+60 #1-16 ((#1)^2)-240 ((#1)^3)+176 ((#1)^4)&,3], ]),(NumericalApproximation[Root, (RowDefault["-2.15", FEExpressionsNumericalApproximationElider]), Root[281961-37751760 ((#1)^2)+44161760 ((#1)^4)-11372800 ((#1)^6)+774400 ((#1)^8)&,2], ])}};
lines={{9,1,3},{15,11,10},{10,3,13},{11,12,6},{12,13,7},{6,4,14},{13,14,8},{7,5,15},{14,15,9},{8,1,11},{6,3,5},{7,4,1},{8,5,2},{10,2,4},{9,2,12}};

Length[lines]

ConfigurationDiagram[pts,lines,.2]

cg=ConfigurationGraph[v,lines,VertexLabels->Automatic]

cgname=RecognizeGraph[cg]

GraphData[cgname,"Graph","Configuration"]

levi=RecognizeGraph@LeviGraph[v,lines]

GraphData[levi,"IncidenceLines"]

RecognizeGraph/@LeviGraph/@%

Embeddings

<<MathWorld`Graphs`

Names

GraphData["CremonaRichmondConfigurationGraph","StandardName"]

GraphData["CremonaRichmondConfigurationGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["CremonaRichmondConfigurationGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Configuration

GraphData["CremonaRichmondConfigurationGraph","Configuration"]

GraphData["CremonaRichmondConfigurationGraph","Graph","Configuration"]//StyleGraphs

config=%[[1]]

alledges=AddAllConfigurationEdges[config]

RecognizeGraph@alledges

ConfigurationDiagram[config,.2]

GraphData["CremonaRichmondConfigurationGraph","IncidenceLines"]

(lines=ConfigurationLines[config])//Timing

r=LeviGraph[lines]//RecognizeGraph

GraphData["CremonaRichmondConfigurationGraph","LeviGraph","Name"]

FirstCase[GraphData[r,"StandardNames"],{"Incidence",_}]

Cases[GraphData["CremonaRichmondConfigurationGraph","StandardNames"],_String?(StringMatchQ[#,"*Configuration*"]&)]

GraphData["CremonaRichmondConfigurationGraph","OrdinaryLineGraphName"]

(ordinarylinegraph=OrdinaryLineGraph[config])//Timing

RecognizeGraph@ordinarylinegraph

Bilateral

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

Circular

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

Circular construction

Length[hc=FindHamiltonianCycle[GraphData["CremonaRichmondConfigurationGraph"],All][[All,All,1]]]

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["CremonaRichmondConfigurationGraph"],#]&/@hc]]//Timing

Planar

GraphData["CremonaRichmondConfigurationGraph","Planar"]

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

MinimalCrossing

GraphData["CremonaRichmondConfigurationGraph",{"RCN","CN"}]

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[%,Max[OuterFace[#]]<=GraphData["CremonaRichmondConfigurationGraph","V"]&]

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

Table[MinimalCrossingGraph[GraphData["CremonaRichmondConfigurationGraph"],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["CremonaRichmondConfigurationGraph","Circulant"]

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

Halin

GraphData["CremonaRichmondConfigurationGraph","Halin"]

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

Rigid

GraphData["CremonaRichmondConfigurationGraph","Rigid"]

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

Flexible

GraphData["CremonaRichmondConfigurationGraph","Flexible"]

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

LCF

GraphData["CremonaRichmondConfigurationGraph","LCF"]

GraphData["CremonaRichmondConfigurationGraph","HamiltonianCycleCount"]

GraphData["CremonaRichmondConfigurationGraph","LCFSignature"]

GraphData["CremonaRichmondConfigurationGraph","LCFNotations"]

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

UnitDistance

GraphData["CremonaRichmondConfigurationGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["CremonaRichmondConfigurationGraph","VertexList"],GraphData["CremonaRichmondConfigurationGraph","EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["CremonaRichmondConfigurationGraph","Matchstick"]

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

3D default

Graph3D[GraphData["CremonaRichmondConfigurationGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["CremonaRichmondConfigurationGraph","Polyhedral"]

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