Square Graph

Author

Eric W. Weisstein
October 16, 2025

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

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

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

Embeddings

<<MathWorld`Graphs`

Names

GraphData["SquareGraph","StandardName"]

GraphData["SquareGraph","StandardNames"]

HouseOfGraphs

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

HouseOfGraphsLookup[hogid]

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

Primary

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

All

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

CurvedEdge

GraphData["SquareGraph","Graph","CurvedEdge"]//StyleGraphs

Inexact

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

Embeddings

GraphDataEmbeddings[GraphData["SquareGraph"]]

Default embedding

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

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

g=FindCorrespondingGraph[,v]

RecognizeGraph@g

Degenerate

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

DegenerateGraphEmbeddingTypes/@GraphData["SquareGraph","Graph","Degenerate"]//Column

GeneralizedPetersen

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

IGraph

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

Bilateral

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

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

Circular

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

Planar

GraphData["SquareGraph","Planar"]

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

Planar construction

PlanarGraphEmbedding[GraphData["SquareGraph"],GraphLayout->#]&/@{"TutteLayout","DavidsonHarelLayout"}

Table[PlanarGraphEmbedding[GraphData["SquareGraph"]],10]

PlanarGraphEmbeddings

GraphData["SquareGraph","PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData["SquareGraph"],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData["SquareGraph"]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData["SquareGraph"],"OuterFace"->#]&/@faces

TextGrid[DeleteCases[{#,GraphSymmetryGroup[#]}&/@gs,{_,TransformationGroup[{}]}],Dividers->All]

Grid[DeleteCases[{#,Cases[GraphSymmetryGroup[#],r_Rotation:>r,∞]}&/@gs,{_,{}}],Dividers->All]

gs=Annotate[#,{VertexLabels->None,ImageSize->Tiny}]&/@{}

RecognizeGraph/@gs

Tutte embedding construction

GraphPlot[RotateGraph[]]

TutteLayoutManipulate[g_Graph]:=Manipulate[
With[{face=OuterFace[g]},
IGLayoutTutte[IGEdgeMap[(EuclideanDistance@@#)^pow&,EdgeWeight->IGEdgeVertexProp[VertexCoordinates],IGLayoutTutte[g,"OuterFace"->face]],"OuterFace"->face,ImageSize->Automatic]],{{pow,1},.1,2}]

TutteLayoutManipulate[]

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

RecognizeGraph[g]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 2

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

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

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

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

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

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

MinimalCrossingNumber: "EmbeddingScheme" -> 3

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

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

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

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

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

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

MinimalCrossingNumber crossings.uos.de

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

ExportString[GraphData["SquareGraph"],"DOT"]

MinimalCrossing

GraphData["SquareGraph","CN"]

gs=GraphData["SquareGraph","Graph","MinimalCrossing"]//StyleGraphs

GraphCrossingCount/@gs

Graphics[{GraphPlot[#,VertexStyle->Automatic][[1]],Red,AbsolutePointSize[5],GraphCrossings[#]}]&/@gs

MinimalRectilinearCrossing

GraphData["SquareGraph","RCN"]

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

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["SquareGraph"],Automatic,All,"Size"->Automatic,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData["SquareGraph"],Automatic,All,"Size"->XXX,Method->"SubgraphIsomorphism",Debug->True]]//Timing

MaxMemoryUsed[]/10^9. GB

Tally[RectilinearCrossingCount/@gs]//Timing

Tally[RectilinearLocalCrossingCount/@gs]//Timing

GraphSymmetryGroup/@gs//Tally

Select[gs,GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]

Take[gs,UpTo[100]]

MinimalCrossing construction Tutte

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

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

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

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

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

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

MinimalCrossing construction Random

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

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData["SquareGraph","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["SquareGraph","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["SquareGraph",{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

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

MinimalRectilinearLocalCrossing

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

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

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

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

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

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

Circulant

GraphData["SquareGraph","Circulant"]

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

Circulant construction

GraphData["SquareGraph","NotationRules","Circulant"]

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

CirculantGraph1@@@ci

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

CirculantGraph1@@@%

Complement graph

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

GraphData[compl,"Graph","All"]

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData["SquareGraph","Line"]

LineGraphQ[GraphData["SquareGraph"]]//Timing

RootGraph

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

RootGraph[GraphData["SquareGraph"]]

RecognizeGraph[%]

GraphData[roots[[1]],"Graph","All"]

gs=LineGraph/@%

Halin

GraphData["SquareGraph","Halin"]

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

Rigid

GraphData["SquareGraph","Rigid"]

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

Flexible

GraphData["SquareGraph","Flexible"]

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

LCF

GraphData["SquareGraph","LCF"]

GraphData["SquareGraph","HamiltonianCycleCount"]

GraphData["SquareGraph","LCFSignature"]

GraphData["SquareGraph","LCFNotations"]

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

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

LCF compute random

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

LCF compute 10^5 [XX GB]

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

gs

BilateralGraphEmbeddingQ/@gs

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{"SquareGraph",{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute 10^6 [XX GB]

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

(nice=SelectFirst[lcf,GraphSymmetryGroup[LCFGraph@@#]=!=TransformationGroup[{}]&])//Timing

l={
{"SquareGraph",{0,Missing["NotAvailable",LCFNotation/@gs]}}
}

PropertyReplace[l,"LCFNotations","14.3"]

RenameGraphFiles[]

LCF compute all

Divisors[GraphData["SquareGraph","V"]]

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

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

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[gs,UnitDistanceGraphEmbeddingQ]

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

NondegenrateSymmetricGraphs=Select[GraphsWithSymmetryGroups[[All,1]],!DegenerateGraphEmbeddingQ[#]&]

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

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance construction via UnitDistanceEmbeddingRefine of exact construction

(unitdistancegraphs=Flatten[With[{step=.1},
Table[
{{a,b,c},
UnitDistanceEmbeddingRefine@Graph[Range[40],ee,VertexCoordinates->N@Join[Sequence@@Table[CirclePoints[Through[{Cos,Sin}[Pi/2-2Pi i/5]],{a,Pi/2-2Pi i/5+2Pi i/6},6],{i,0,4}],CirclePoints[b,5],CirclePoints[c,5]]]},
{a,step,2,step},{b,step,2,step},{c,step,2,step}
]],2]);//Quiet//Timing

{Length[unitdistancegraphs],Count[unitdistancegraphs,_?(UnitDistanceGraphEmbeddingQ[Last[#]]&)]}

RandomSample[unitdistancegraphs,10]

Select[unitdistancegraphs,DegenerateGraphEmbeddingQ[Last[#]]===False&]//Timing

MinimumDistance[v_]:=Min[EuclideanDistance@@@Subsets[v,{2}]]

distances=MinimumDistance[GraphEmbedding[#]]&/@unitdistancegraphs[[All,-1]];

Histogram[distances]

Max[distances]

Position[distances,Max[distances]]

Take[ReverseSortBy[Transpose[{distances,unitdistancegraphs}],First],10]

UnitDistanceGraphEmbeddingQ/@gs

DegenerateGraphEmbeddingTypes/@gs

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

gs=SortBy[UniqueEmbeddings[l],Replace[RectilinearCrossingCount[#],Infinity->0]&]

Select[IndexGraph/@gs,!DegenerateGraphEmbeddingQ[#]&&GraphSymmetryGroup[#]=!=TransformationGroup[{}]&]//Timing

Matchstick

GraphData["SquareGraph","Matchstick"]

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

3D default

Graph3D[GraphData["SquareGraph","Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["SquareGraph","Polyhedral"]

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

GraphData

GraphDataClassString

GraphDataClassString["SquareGraph"]