Petersen Line Graph

Author

Eric W. Weisstein
May 2, 2026

This notebook downloaded from https://mathworld.wolfram.com/notebooks/GraphTheory/PetersenLineGraph.nb.

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["PetersenLineGraph","StandardName"]

GraphData["PetersenLineGraph","StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData["PetersenLineGraph","WikidataID"]

GraphData["PetersenLineGraph","WikidataID","URL"]

Primary

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

Read and Wilson construction

g=Graph[Range[15],UndirectedEdge@@@{{1,2},{1,3},{1,4},{1,9},{2,3},{2,6},{2,8},{3,7},{3,13},{4,5},{4,9},{4,10},{5,7},{5,10},{5,11},{6,8},{6,11},{6,12},{7,11},{7,13},{8,10},{8,14},{9,12},{9,15},{10,14},{11,12},{12,15},{13,14},{13,15},{14,15}},VertexCoordinates->(10^(-4)){{8071,-7463},{10495,-11619},{10976,-16406},{12473,-5526},{12871,-10846},{13942,-7548},{15675,-15384},{15675,-12884},{15675,-1935},{17407,-7548},{18478,-10846},{18876,-5526},{20373,-16406},{20854,-11619},{23278,-7463}}]

RecognizeGraph@g

All

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

Inexact

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

Max[Abs[EdgeLengths[#]-1]]&/@%

Degenerate

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

Embedding types

GraphDataEmbeddings[GraphData["PetersenLineGraph","EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData["PetersenLineGraph","Edges"],-Pi/4]

v=Join[UnitCirclePoints[10,-Pi/2],CirclePoints[1,4],{{0,0}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[{1,10},1,11,5,7,14,1],e[8,14,2,12,13,10,11,4,15,9,13,6,12,3,15,8]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

v=Join[UnitCirclePoints[5],CirclePoints[{1/2,-Pi/2},5],CirclePoints[{1/4,-Pi/2},5]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,7,2,8,3,9,4,10,5,6,1],e[10,11,7,13,9,15,6,12,8,14,10],e[11,13,15,12,14,11]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Construction as a line graph

LineGraph/@GraphData["PetersenGraph","Graph","All"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Bilateral

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

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

Circular

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

Planar

GraphData["PetersenLineGraph","Planar"]

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

Construction from distanceregular.org

g=DistanceRegularGraph["line-petersen"]

RecognizeGraph[g]

Circulant

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

Halin

GraphData["PetersenLineGraph","Halin"]

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

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossingNumber crossings.uos.de [verified 7]

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

ExportString[GraphData["PetersenLineGraph"],"DOT"]

-------- Forwarded Message --------
Subject: 	[crossings.uos.de] P line succeeded
Date: 	Sat, 04 Oct 2025 14:13:53 +0200
From: 	confirm@vm524.rz.uni-osnabrueck.de
To: 	eww@wolfram.com
CC: 	mirwagner@uos.de, markus.chimani@uos.de

Dear Eric Weisstein,

we have successfully computed the crossing number of your graph (P line).
The graph has a crossing number of 7.

Please visit this link for detailed results: https://crossings.uos.de/job/TogSu47t8zhL6fPJlDk1JQ

MinimalCrossing

GraphData["PetersenLineGraph","CN"]

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

MinimalRectilinearCrossing

GraphData["PetersenLineGraph","RCN"]

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

MinimalCrossing construction

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

Tutte:

(g=MinimalCrossingGraph[GraphData["PetersenLineGraph"],"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["PetersenLineGraph","V"]])]
}&/@TutteGraphs;

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

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

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

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

Random:

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["PetersenLineGraph","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["PetersenLineGraph","V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

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

GraphPlot@

v={#/6,#2/4}&@@@{{0,0},{6,0},{1,1},{3,1},{5,1},{1,2},{3,2},{5,2},{1,3},{2,3},{4,3},{5,3},{0,4},{3,4},{6,4}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,15,14,13,1,4,2,5,8,12,11,10,9,6,3,1],e[10,6,7,8,11,4,10],e[3,13,12],e[5,15,9,14,12],e[3,7,5]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot[MinimalCrossingGraph[GraphData["PetersenLineGraph"],"CrossingNumber"->7]]

GraphPlot@

v={#/6,#2/5}&@@@{{0,0},{6,0},{1,1},{3,1},{5,1},{3,2},{1,3},{2,3},{4,3},{5,3},{1,4},{3,4},{5,4},{0,5},{6,5}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,15,11,12,13,14,1,3,7,11],e[13,10,5,2,6,1],e[7,8,9,10,4,7],e[3,4,5,15],e[11,8,6,9,13],e[3,14,12,15]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot[MinimalCrossingGraph[GraphData["PetersenLineGraph"],"CrossingNumber"->7]]

GraphPlot@

v={#/6,#2/5}&@@@{{0,0},{6,0},{3,1},{1,2},{3,2},{5,2},{1,3},{2,3},{4,3},{5,3},{1,4},{3,4},{5,4},{0,5},{6,5}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,15,11,12,13,14,1,4,7,11],e[13,10,6,2,3,1],e[14,4,5,6,15],e[7,8,9,10,5,7],e[15,12,14],e[11,8,3,9,13]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot[MinimalCrossingGraph[GraphData["PetersenLineGraph"],"CrossingNumber"->7]]

GraphPlot@

v=Join[{{-1,0},{1,0},{0,Sqrt[3]},{-1/2,1/4},{0,1/4},{1/2,1/4},{-1/2,1/2},{1/2,1/2},{-1/8,1/2},{1/8,1/2}},Subdivide[{-1/4,3/4},{1/4,3/4},3],{{0,5/4}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,15,1,4,5,6,2,8,14,13,12,11,7,1],e[4,7,3,8,6,9,11,3,14,10,4],e[15,12,9,5,10,13,15]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

GraphPlot[MinimalCrossingGraph[GraphData["PetersenLineGraph"],"CrossingNumber"->7]]

GraphPlot@

v=Join[{{-1,0},{1,0},{0,Sqrt[3]},{-1/2,1/4},{-1/4,1/4},{1/4,1/4},{1/2,1/4},{-1/4,1/2},{0,1/2},{1/4,1/2}},Subdivide[{-1/4,3/4},{1/4,3/4},3],{{0,5/4}}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,15,1,5,9,6,2,7,14,3,11,4,1],e[4,5,10,14,13,12,11,8,6,7],e[4,3,7],e[8,12,15,13,10],e[8,9,10]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

RectilinearLocalCrossingCount[g]

gs=UnlabelGraph/@{,,,,}

GraphPlot[MinimalCrossingGraph[GraphData["PetersenLineGraph"],"CrossingNumber"->7]]

e[l__]:=Sequence@@Partition[{l},2,1]

v={{0,0},{8,0},{4,1},{4,2},{1,3},{2,3},{3,3},{5,3},{6,3},{7,3},{0,4},{5,4},{3,5},{8,5},{4,6}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,14,15,11,1,5,6,7,8,9,10,14,13,15,12,8,4,1],e[11,12,9,3,5,11],e[3,6,13,7],e[2,4,7],e[3,10,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

MinimalLocalCrossing

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

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

MinimalRectilinearLocalCrossing

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

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

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

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

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

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

LCF

GraphData["PetersenLineGraph","LCF"]

GraphData["PetersenLineGraph","LCFSignature"]

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

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

LCF compute

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

Tally[(lcf=LCF[GraphData["PetersenLineGraph"],All])[[All,2]]]//Timing

gs=LCFGraph@@@lcf//StyleGraphs

gs=Join[With[{g=BilateralLCFEmbedding[#]},If[MissingQ[g],#,g]]&/@LCFGraph@@@DeleteCases[lcf,{_,1}],DeleteMissing[BilateralLCFEmbedding/@LCFGraph@@@Cases[lcf,{_,1}]]]

UnitDistance

GraphData["PetersenLineGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[gs,UnitDistanceGraphEmbeddingQ]

DeleteCases[{BilateralGraph[CenterGraph@#,"ReturnNonbilateralGraph"->True],GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}]

%[[All,1]]

LabelGraph/@{,,,,,,,}

gs=UnlabelGraph/@{RotateGraph[,{2,4}],RotateGraph[,{9,13}],,,}

UnitDistance by FindUnitDistanceEmbedding

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

g=RotateGraph[,{15,1}]

EdgeLengths[g]

DegenerateGraphEmbeddingTypes@g

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData["PetersenLineGraph","Matchstick"]

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

Default embedding

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

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

RecognizeGraph[g]

3D default

Graph3D[GraphData["PetersenLineGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["PetersenLineGraph","Polyhedral"]

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

GraphData

GraphDataClassString

GraphDataClassString["PetersenLineGraph"]