Utility Graph

Author

Eric W. Weisstein
March 28, 2023

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

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

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

Embeddings

GraphData["UtilityGraph","StandardName"]

Primary

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

Read and Wilson

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["UtilityGraph","EdgeList"]]

Default embedding

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

v={};
g=Graph[Range[Length[v]],Sort[Sort/@(UndirectedEdge@@@{Sequence@@curvededges={}})],VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["UtilityGraph"],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

Length[quad=DeleteDuplicatesBy[Union@Select[bilat,BilateralGraphEmbeddingQ[#,Axis->"X"]&],CircularCanonicalGraphEmbedding[#,4]&]]

quad

Planar

GraphData["UtilityGraph","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

GraphPlot@RotateGraph[,-Pi/4]

GraphPlot@RotateGraph[,-Pi/2]

v=Join[{{-1,0},{1,0},{0,Sqrt[3]}},Table[{i/3,2/3},{i,-1,1}]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,3,2,4,5,6,1,4],{2,6},{3,5}},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["UtilityGraph","Circulant"]

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

Halin

GraphData["UtilityGraph","Halin"]

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

Rigid

GraphData["UtilityGraph","Rigid"]

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

Flexible

GraphData["UtilityGraph","Flexible"]

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

LCF

GraphData["UtilityGraph","LCF"]

GraphData["UtilityGraph","HamiltonianCycleCount"]

GraphData["UtilityGraph","LCFSignature"]

GraphData["UtilityGraph","LCFNotations"]

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

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

LCF compute all

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

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

MaxMemoryUsed[]/10.^9 "GB"

lcf

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

(gs=Flatten[{
(* all LCF's with order >1, sorted by order and with bilateral graphs first *)
Join[DeleteCases[#,{_Missing,_}][[All,1]],Cases[#,{_Missing,_}][[All,2]]]&/@Map[{BilateralLCFGraph@#,#}&,Map[LCFGraph@@#&,SplitBy[DeleteCases[lcf,{_,1}],Last],{2}],{2}],
(* order-1 bilateral only *)
DeleteMissing[BilateralLCFGraph@@@Cases[lcf,{_,1}]]}])//Timing

Length[gs]

UnitDistance

GraphData["UtilityGraph","UnitDistance"]

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

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

UnitDistance by refinement

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

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

UnitDistance by FindUnitDistanceEmbedding

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

Matchstick

GraphData["UtilityGraph","Matchstick"]

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

3D default

Graph3D[GraphData["UtilityGraph","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["UtilityGraph","Polyhedral"]

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

GrapData

Matrices

GraphicsRow[GraphMatrixPlot[GraphData["UtilityGraph"]]]

Subject

GraphClassString["UtilityGraph"]