Ljubljana Graph

Author

Eric W. Weisstein
November 10, 2023

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

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

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

Embeddings

Names

GraphData["LjubljanaGraph","StandardName"]

GraphData["LjubljanaGraph","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["LjubljanaGraph","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Perspective

GraphData["LjubljanaGraph","Graph","Perspective"]//StyleGraphs

Perspective construction

GraphData["LjubljanaGraph","Polyhedron"]

Bilateral

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

Circular

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

Planar

GraphData["LjubljanaGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["LjubljanaGraph","Circulant"]

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

Complement graph

GraphData["LjubljanaGraph","ComplementGraph","Name"]

Line graph

GraphData["LjubljanaGraph","Line"]

LineGraphQ[GraphData["LjubljanaGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["LjubljanaGraph"]]

Halin

GraphData["LjubljanaGraph","Halin"]

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

Rigid

GraphData["LjubljanaGraph","Rigid"]

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

Flexible

GraphData["LjubljanaGraph","Flexible"]

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

LCF

GraphData["LjubljanaGraph","LCF"]

GraphData["LjubljanaGraph","HamiltonianCycleCount"]

GraphData["LjubljanaGraph","LCFSignature"]

GraphData["LjubljanaGraph","LCFNotations"]

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

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

LCF compute random

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

LCF compute 10^5

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

LCF compute all

Divisors[GraphData["LjubljanaGraph","V"]]

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

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

MaxMemoryUsed[]/10.^9 "GB"

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

DeleteCases[lcf,{_,1}]

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

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

Length[gs]

gs

gs=LCFGraph@@@Take[lcf,1]

UnitDistance

GraphData["LjubljanaGraph","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance FindSubgraphUnitDistanceEmbedding

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

gs=UniqueEmbeddings[l]

Matchstick

GraphData["LjubljanaGraph","Matchstick"]

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

3D default

Graph3D[GraphData["LjubljanaGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["LjubljanaGraph","Polyhedral"]

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

Construction

Construction from Condor et al., p. 12

l=;

Table[LinesToGraph[l,x],{x,.2,2,.1}]

g=LinesToGraph[l,2]

Degrees[g]

non3=Flatten[Position[Degrees[g],Except[3],1,Heads->False]]

(me=Function[v,Select[Edges[g],MemberQ[#,v]&]]/@non3)//Column

Graphics[Point[pts=First/@Partition[Cases[l,_Polygon,{1,∞}]/.Polygon[x_]:>Mean[x],2]]]

Graphics[Line[lines=First/@Cases[l,_Line,{1,∞}]]]

edges=Sort[Sort/@Flatten/@Map[Nearest[Thread[pts->Range[112]],#,1]&,lines,{2}]]

Length[edges]

rg=RecognizeGraph[g=Graph[List/@edges,List/@pts]]

ShowGraph[g,VertexStyle->Disk[.02]]

Ljubljana Configuration

Import["/Volumes/Users/eww/Desktop/conder02ljubljana.pdf",{"Pages",13}]

l={,};

gs=LinesToGraph[#,1]&/@l

RecognizeGraph/@gs

GraphData

GraphClassString

GraphClassString["LjubljanaGraph"]

GraphDataMatrices

GraphDataMatrices["LjubljanaGraph"]

GraphDataTable

TableForm[GraphDataTable["LjubljanaGraph",x],TableDepth->2]//TraditionalForm

GraphDataString

Print[GraphDataString[g,
"Name"->"Ljubljana graph",
"StandardName"->"LjubljanaGraph",
TimeConstraint->120,
Debug->True
]]