Truncated Square Lattice Graph

Author

Eric W. Weisstein
February 13, 2026

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

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

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

Sources

Howroyd 2026

From Andrew Howroyd, Feb. 13, 2026

Is there a name for the 2d version of the n-necklace graph? (which might be interesting too). Consists of grid of 4-cycles connected in a torus.
For example for 2 X 3:
        |       |       |
        o       o       o
       / \     / \     / \
   ---o   o---o   o---o   o---
       \ /     \ /     \ /
        o       o       o
        |       |       |
        o       o       o
       / \     / \     / \
   ---o   o---o   o---o   o---
       \ /     \ /     \ /
        o       o       o
        |       |       |


With the left side connected to the right and the top to the bottom. (if only one layer this is the n-necklace graph). 
Also a truncated square tiling confined to a torus.

Razzoli et al. 2020

https://scispace.com/pdf/continuous-time-quantum-walks-on-planar-lattices-and-the-3kzdgelny0.pdf

RAZZOLI, PARIS, AND BORDONE PHYSICAL REVIEW A 101, 032336 (2020)

Figure

GraphicsGrid[
StyleGraphs@Table[Annotate[TruncatedSquareLatticeGraph[m,n],PlotLabel->Row[{m,"×",n}]],{m,3},{n,4}],
Dividers->All,Alignment->Top,BaseStyle->InsetBoxOptions->{BaseStyle->Directive[LightDarkSwitched@Black,14,FontFamily->"Times"]}
]

Special cases

<<MathWorld`Graphs`

GraphData

Generate

TextGrid[truncatedsquares=DeleteCases[
Flatten[Table[{{m,n},RecognizeGraph@TruncatedSquareLatticeGraph[m,n]},{m,10},{n,m,10}],1],
{_,{}}
],
Dividers->All]

Embeddings

<<MathWorld`Graphs`

{"TruncatedSquareLattice", {1, 1}} == "TetrahedralGraph"

Names

GraphData[{"TruncatedSquareLattice",{1,1}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,1}},"StandardNames"]

{"TruncatedSquareLattice", {1, 2}} == {"Necklace", 2}

Names

GraphData[{"TruncatedSquareLattice",{1,2}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,2}},"StandardNames"]

{"TruncatedSquareLattice", {1, 3}} == {"Necklace", 3}

Names

GraphData[{"TruncatedSquareLattice",{1,3}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,3}},"StandardNames"]

{"TruncatedSquareLattice", {1, 4}} == {"Necklace", 4}

Names

GraphData[{"TruncatedSquareLattice",{1,4}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,4}},"StandardNames"]

{"TruncatedSquareLattice", {1, 5}} == {"Necklace", 5}

Names

GraphData[{"TruncatedSquareLattice",{1,5}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,5}},"StandardNames"]

{"TruncatedSquareLattice", {1, 6}} == {"Necklace", 6}

Names

GraphData[{"TruncatedSquareLattice",{1,6}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,6}},"StandardNames"]

{"TruncatedSquareLattice", {1, 7}} == {"Necklace", 7}

Names

GraphData[{"TruncatedSquareLattice",{1,7}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,7}},"StandardNames"]

{"TruncatedSquareLattice", {1, 8}} == {"Necklace", 8}

Names

GraphData[{"TruncatedSquareLattice",{1,8}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,8}},"StandardNames"]

{"TruncatedSquareLattice", {1, 9}} == {"Necklace", 9}

Names

GraphData[{"TruncatedSquareLattice",{1,9}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,9}},"StandardNames"]

{"TruncatedSquareLattice", {1, 10}} == {"Necklace", 10}

Names

GraphData[{"TruncatedSquareLattice",{1,10}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{1,10}},"StandardNames"]

{"TruncatedSquareLattice", {2, 2}} == {"CrossedPrism", 8}

Names

GraphData[{"TruncatedSquareLattice",{2,2}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{2,2}},"StandardNames"]

{"TruncatedSquareLattice", {2, 3}}

Names

GraphData[{"TruncatedSquareLattice",{2,3}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{2,3}},"StandardNames"]

HouseOfGraphs

hogid=GraphData[{"TruncatedSquareLattice",{2,3}},"NotationRules","HouseOfGraphs"]

HouseOfGraphsLookup[hogid]

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

Wikidata

GraphData[{"TruncatedSquareLattice",{2,3}},"WikidataID"]

GraphData[{"TruncatedSquareLattice",{2,3}},"WikidataID","URL"]

TruncatedSquareLattice construction

g=TruncatedSquareLatticeGraph[2,3]

Primary

GraphData[{"TruncatedSquareLattice",{2,3}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","All"]//StyleGraphs

CurvedEdge

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","CurvedEdge"]//StyleGraphs

Inexact

Select[GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Degenerate

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Degenerate"]//StyleGraphs

DegenerateGraphEmbeddingTypes/@GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Degenerate"]//Column

Embeddings

GraphDataEmbeddings[GraphData[{"TruncatedSquareLattice",{2,3}}]]

Default embedding

g0=GraphPlot[Graph[GraphData[{"TruncatedSquareLattice",{2,3}},"VertexList"],GraphData[{"TruncatedSquareLattice",{2,3}},"Edges"]]]

GeneralizedPetersen

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","GeneralizedPetersen"]//StyleGraphs

IGraph

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","IGraph"]//StyleGraphs

CompleteKPartite

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","CompleteKPartite"]//StyleGraphs

Bipartite

GraphData[{"TruncatedSquareLattice",{2,3}},"Bipartite"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Bipartite"]

Bipartite construction

GraphData[{"TruncatedSquareLattice",{2,3}},"Bipartite"]

g0=Graph[GraphData[{"TruncatedSquareLattice",{2,3}},"VertexList"],GraphData[{"TruncatedSquareLattice",{2,3}},"Edges"],GraphLayout->"BipartiteEmbedding"]

v=With[{n=Ceiling[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]/2]},Flatten[Table[{i,j/n},{i,{-1,1}/2},{j,0,n}],1]];

g=FindCorrespondingGraph[g0,v]

RecognizeGraph@g

Bilateral

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Bilateral"]//StyleGraphs

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

Circular

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Circular"]//StyleGraphs

Circular construction 10^3

Length[hc=FindHamiltonianCycle[GraphData[{"TruncatedSquareLattice",{2,3}}],10^3][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"TruncatedSquareLattice",{2,3}}],#]&/@hc);//Timing

GraphWithSymmetryGroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[GraphWithSymmetryGroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilateralGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[GraphWithSymmetryGroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

MaxMemoryUsed[]/10^9.GB

Circular construction All

GraphData[{"TruncatedSquareLattice",{2,3}},"Hamiltonian"]

GraphData[{"TruncatedSquareLattice",{2,3}},"LCF"]

GraphData[{"TruncatedSquareLattice",{2,3}},"HamiltonianCycleCount"]

Length[hc=FindHamiltonianCycle[GraphData[{"TruncatedSquareLattice",{2,3}}],All][[All,All,1]]]//Timing

(circ=CircularEmbeddingFromHamiltonianCycle[GraphData[{"TruncatedSquareLattice",{2,3}}],#]&/@hc);//Timing

GraphWithSymmetryGroups={#,GraphSymmetryGroup[#]}&/@circ;//Timing

Tally[GraphWithSymmetryGroups[[All,-1]]]//Column

(BilateralOrRotationalGraphs={BilateralGraph[#,"ReturnNonbilateralGraph"->True],#2}&@@@SortBy[
DeleteCases[GraphWithSymmetryGroups,{_,TransformationGroup[{}]}],
{MatchQ[#[[2]],TransformationGroup[{_Rotation,r_Reflection}|{r_Reflection|_Rotation}]],FirstCase[#[[2]],Rotation[{0,0},r_]:>N[r/π],{},{0,∞}]}&
])//Timing

Length[SymmetricGraphs=DeleteDuplicatesBy[BilateralOrRotationalGraphs,CircularCanonicalGraphEmbedding[#[[1]]]&]]//Timing

SymmetricGraphs

Length[BilateralGraphs=Select[SymmetricGraphs,!FreeQ[#,Reflection]&][[All,1]]]

BilateralGraphs

Length[BilateralAndRotationalGraphs=Select[SymmetricGraphs,And[!FreeQ[#,Rotation],!FreeQ[#,Reflection]]&][[All,1]]]

BilateralAndRotationalGraphs

Circular construction old

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilateralGraph/@circ],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

quad

Planar

GraphData[{"TruncatedSquareLattice",{2,3}},"Planar"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Planar"]//StyleGraphs

Planar construction

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

Table[PlanarGraphEmbedding[GraphData[{"TruncatedSquareLattice",{2,3}}]],10]

PlanarGraphEmbeddings

GraphData[{"TruncatedSquareLattice",{2,3}},"PlanarEmbeddingCount"]

(plemb=PlanarGraphEmbeddings[GraphData[{"TruncatedSquareLattice",{2,3}}],Debug->True])//Timing

Length[plemb]

Tutte embeddings

faces=ReverseSort@SymmetricallyDistinctFaces[GraphData[{"TruncatedSquareLattice",{2,3}}]]

Tally[ReverseSort[Length/@faces]]

gs=IGLayoutTutte[GraphData[{"TruncatedSquareLattice",{2,3}}],"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 crossings.uos.de

CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],Method->"WebCompute"]//AbsoluteTiming

DateString[]

MinimalCrossingNumber: "EmbeddingScheme" -> 1

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->1,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 2

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->2,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossingNumber: "EmbeddingScheme" -> 3

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->1])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->10])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->60])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->5 3600])//AbsoluteTiming

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],"EmbeddingScheme"->3,TimeConstraint->86400])//AbsoluteTiming

MinimalCrossing

GraphData[{"TruncatedSquareLattice",{2,3}},"CN"]

(gs=GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","MinimalCrossing"])//StyleGraphs

GraphCrossingCount/@gs

GraphCrossingDiagram/@gs

MinimalRectilinearCrossing

GraphData[{"TruncatedSquareLattice",{2,3}},"RCN"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","MinimalRectilinearCrossing"]//StyleGraphs

MinimalRectilinearCrossing construction order X [minimum RCN == ]

Length[gs=FindMinimalRectilinearCrossingGraph[GraphData[{"TruncatedSquareLattice",{2,3}}],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[{"TruncatedSquareLattice",{2,3}}],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[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->1])//AbsoluteTiming

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

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

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

LocalCrossingNumberWithEmbeddings=
{1+Max[Length/@DeleteCases[
Drop[AdjacencyList[#],GraphData[{"TruncatedSquareLattice",{2,3}},"V"]],
_Integer?(LessEqualThan[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]]),
{2}
]],#}&/@TutteGraphs

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

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

Select[SymmetricEmbeddingsWithOrientations[[All,1]],Count[OuterFace[#],_?(GreaterThan[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]])]==0&]

MinimalCrossing construction Random 1k

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->1])//AbsoluteTiming

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

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

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

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"TruncatedSquareLattice",{2,3}},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

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

MinimalCrossing construction Random 20k

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->1])//AbsoluteTiming

(RandomGraphs=Table[MinimalCrossingGraph[GraphData[{"TruncatedSquareLattice",{2,3}}],"CrossingNumber"->cn,RandomSeed->n],{n,20000}]//Union);//Timing

RandomGraphsWithOuterCrossingPointCounts={
#,
Count[OuterFace[#],_?(GreaterThan[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]])]
}&/@RandomGraphs;

Small numbers of crossing points on the boundary:

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

Cases[RandomGraphsWithOuterCrossingPointCounts,{g_,1}:>g]

Symmetric embeddings:

RandomGraphsWithSymmetryGroups={
#,
GraphSymmetryGroup[
#,
AdditionalData->Join[Table[True,GraphData[{"TruncatedSquareLattice",{2,3}},"V"]],Table[False,cn]],
SameTest->Equal
]
}&/@RandomGraphs;

MaxMemoryUsed[]/10^9.GB

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

MinimalLocalCrossing

GraphData[{"TruncatedSquareLattice",{2,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","MinimalLocalCrossing"]//StyleGraphs

MinimalRectilinearLocalCrossing

GraphData[{"TruncatedSquareLattice",{2,3}},{"LocalCrossingNumber","RectilinearLocalCrossingNumber"}]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","MinimalRectilinearLocalCrossing"]//StyleGraphs

MinimaRectilinearlLocalCrossing construction 1000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->10])//AbsoluteTiming

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

MinimaRectilinearlLocalCrossing construction 20000

AdjacentCrossingsQ[g_Graph,cn_Integer]:=Module[{a=AdjacencyList[g],n=VertexCount[g]-cn},Max[Take[a,-cn]]>n]

(cn=CrossingNumber[GraphData[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->10])//AbsoluteTiming

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

Circulant

GraphData[{"TruncatedSquareLattice",{2,3}},"Circulant"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Circulant"]//StyleGraphs

Circulant construction

GraphData[{"TruncatedSquareLattice",{2,3}},"NotationRules","Circulant"]

(ci=CirculantIndices[GraphData[{"TruncatedSquareLattice",{2,3}}]])//Timing

CirculantGraph1@@@ci

Cases[GraphData[{"TruncatedSquareLattice",{2,3}},"StandardNames"],{"Circulant",i_}:>i]

CirculantGraph1@@@%

Complement graph

compl=GraphData[{"TruncatedSquareLattice",{2,3}},"ComplementGraph","Name"]

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

gs=GraphComplement/@%

Select[%,!DegenerateGraphEmbeddingQ[#]&]

Line graph

GraphData[{"TruncatedSquareLattice",{2,3}},"Line"]

LineGraphQ[GraphData[{"TruncatedSquareLattice",{2,3}}]]//Timing

RootGraph

roots=Select[GraphData[All],GraphData[#,"LineGraph","Name"]==={"TruncatedSquareLattice",{2,3}}&]

RootGraph[GraphData[{"TruncatedSquareLattice",{2,3}}]]

RecognizeGraph[%]

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

gs=LineGraph/@%

Halin

GraphData[{"TruncatedSquareLattice",{2,3}},"Halin"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Halin"]//StyleGraphs

Rigid

GraphData[{"TruncatedSquareLattice",{2,3}},"Rigid"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Rigid"]//StyleGraphs

Flexible

GraphData[{"TruncatedSquareLattice",{2,3}},"Flexible"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Flexible"]//StyleGraphs

LCF

GraphData[{"TruncatedSquareLattice",{2,3}},"LCF"]

GraphData[{"TruncatedSquareLattice",{2,3}},"HamiltonianCycleCount"]

GraphData[{"TruncatedSquareLattice",{2,3}},"LCFSignature"]

GraphData[{"TruncatedSquareLattice",{2,3}},"LCFNotations"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","LCF"]//StyleGraphs

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

LCF compute random

FindRandomLCFNotation[GraphData[{"TruncatedSquareLattice",{2,3}}],TimeConstraint->120]

LCF compute 10^5 [XX GB]

Tally[(lcf=LCF[GraphData[{"TruncatedSquareLattice",{2,3}}],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

LCF compute 10^6 [XX GB]

Tally[(lcf=LCF[GraphData[{"TruncatedSquareLattice",{2,3}}],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

LCF compute all

Divisors[GraphData[{"TruncatedSquareLattice",{2,3}},"V"]]

Length[FindHamiltonianCycle[GraphData[{"TruncatedSquareLattice",{2,3}}],All][[All,All,1]]]//Timing

Tally[(lcf=LCF[GraphData[{"TruncatedSquareLattice",{2,3}}],All])[[All,2]]]//Timing

MaxMemoryUsed[]/10.^9 "GB"

DeleteCases[lcf,{_,1}]

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

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

Length[gs=nicelcfgs]

gs

NiceLCFEmbeddingsWithSymmetryGroups={#,GraphSymmetryGroup[#]}&/@gs;

DeleteCases[NiceLCFEmbeddingsWithSymmetryGroups,{_,TransformationGroup[{Reflection[InfiniteLine[{0,0},{0,-1}]]}]}]

UnitDistance

GraphData[{"TruncatedSquareLattice",{2,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"TruncatedSquareLattice",{2,3}}],Debug->True]//Timing

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement of default embeddings

Graph[edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"TruncatedSquareLattice",{2,3}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

Graph[vertex list, edge list]

(g=UnitDistanceEmbeddingRefine[Graph[GraphData[{"TruncatedSquareLattice",{2,3}},"VertexList"],GraphData[{"TruncatedSquareLattice",{2,3}},"EdgeList"]],MaxIterations->500])//Timing

UnitDistanceGraphEmbeddingQ[g]

UnitDistance by refinement of existing embeddings

gs=UnitDistanceEmbeddingRefine[#,MaxIterations->500]&/@Complement@@(GraphData[{"TruncatedSquareLattice",{2,3}},"Graph",#]&/@{"All","UnitDistance"})

TextGrid[
gdata=SortBy[
{#,DegenerateGraphEmbeddingQ[#],GraphSymmetryGroup[#],Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
],
Dividers->All
]

Cases[gdata,{__,0.}]

Symmetric:

gs=Cases[
gdata,
{g_,_,sym:Except[TransformationGroup[{}]],diff_}:>{
HighlightGraph[g1=BilateralGraph[CenterGraph[g],"ReturnNonbilateralGraph"->True],Flatten[FindCoincidentVertices[g1]]],
sym,
diff
}]

UnitDistance by refinement of stored LCF embeddings

FileByteCount[file="/Volumes/GraphProperties/Properties/LCFNotations/"<>GraphNameToFileName[{"TruncatedSquareLattice",{2,3}}]<>".gz"]

Tally[(lcf=Import[file])[[All,-1]]]//Timing//AbsoluteTiming

lcf=LCFNotation/@nicelcfgs;

gs=UnitDistanceEmbeddingRefine[LCFGraph@@#,MaxIterations->500]&/@lcf;//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

NondegenerateSymmetricGraphs=Select[
gdata,
And[
DegenerateGraphEmbeddingQ[#[[1]]]===False,
GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]
]&
]/.g_Graph:>CenterGraph[g]

UnitDistance by FindUnitDistanceEmbedding  (random embeddings returning on messages)

gs=FindUnitDistanceEmbedding[GraphData[{"TruncatedSquareLattice",{2,3}}],50,"ReturnWithMessage"->True];//Quiet//Timing

gdata=SortBy[
{#,Max[Abs[EdgeLengths[#]-1]]}&/@gs,
Last
]

Cases[gdata,{g_?UnitDistanceGraphEmbeddingQ,_}:>g]

SymmetricEmebddings=Select[gdata,GraphSymmetryGroup[#[[1]]]=!=TransformationGroup[{}]&]

UnitDistance by FindUnitDistanceEmbedding  (random embedding waiting until UD is found)

FindUnitDistanceEmbedding[GraphData[{"TruncatedSquareLattice",{2,3}}],"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

{$Version,DateString[]}

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

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

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

Matchstick

GraphData[{"TruncatedSquareLattice",{2,3}},"Matchstick"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"TruncatedSquareLattice",{2,3}},"Edges"]]

3D construction

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

RecognizeGraph[g]

3D All

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph",{"3D","All"}]

3D UnitDistance construction Random

GraphData[{"TruncatedSquareLattice",{2,3}},"Dimension"]

(g=UnitDistanceEmbeddingRefine[
Graph3D[
GraphData[{"TruncatedSquareLattice",{2,3}},"VertexList"],
GraphData[{"TruncatedSquareLattice",{2,3}},"EdgeList"]
],
WorkingPrecision->25])//Timing

EdgeLengths[g]

UnitDistanceGraphEmbeddingQ[g]

3D UnitDistance

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"TruncatedSquareLattice",{2,3}},"Polyhedral"]

GraphData[{"TruncatedSquareLattice",{2,3}},"Graph",{"3D","Polyhedron"}]

{"TruncatedSquareLattice", {4, 4}} == {"CubeConnectedCycle", 4}

Names

GraphData[{"TruncatedSquareLattice",{4,4}},"StandardName"]

GraphData[{"TruncatedSquareLattice",{4,4}},"StandardNames"]

Construction

TruncatedSquareLatticeGraph[3,4]

GridGraph[{3,4}]

PropertyValue[,EdgeShapeFunction]

<<MathWorld`Graphs`

CurvedEdgeData[]

PropertyValue[,EdgeShapeFunction]

GraphData

GraphDataClassString

GraphDataClassString["TruncatedSquareLattice"]

GraphDataString

all=Sort[{#,RecognizeGraph[TruncatedSquareLatticeGraph@@#]}&/@Flatten[Table[{m,n},{n,10},{m,n}],1]]

add=Cases[all,{ind_,{}}:>ind]

file=OpenAppend["~/truncated-square.m"]

add={{9,9},{9,10},{10,10}};

WriteString[
file,
GraphDataString[
TruncatedSquareLatticeGraph[#,#2],
"StandardName"->{"TruncatedSquareLattice",{##}},
"Name"->"("<>ToString[#]<>","<>ToString[#2]<>")\[Hyphen]truncated square lattice graph",
"Classes"->{"TruncatedSquareLattice"},
"NotationRules"->{"TruncatedSquareLattice"->{##}},
"Information"->"TruncatedSquareLatticeGraph",
TimeConstraint->10,
Debug->True,
"Skip"->{"ABCEnergy","ABCSpectralRadius","ArithmeticGeometricEnergy","ArithmeticGeometricSpectralRadius","CharacteristicPolynomial","ChordlessCycles","ComplementChordlessCycles","ComplementOddChordlessCycles","ConnectedInducedSubgraphPolynomial","ConnectedInducedSubgraphs","ConstructionNumber","CoolingNumber","Cycles","CyclicEdgeConnectivity","DominatingSets","EdgeBetweennessCentralities","Energy","ErdoSequence","FeedbackVertexSetNumber","GracefulLabeling","GracefulLabelingCount","HamiltonianPaths","IndependencePolynomial","IndependentEdgeSets","IndependentVertexSets","IrredundancePolynomial","IrredundantSets","LongestCycles","MatchingGeneratingPolynomial","MaximalIndependencePolynomial","MaximalIndependentEdgeSets","MaximalIndependentVertexSets","MaximumIndependentEdgeSetCount","MaximumIndependentEdgeSets","MaximumIndependentVertexSets","MaximumIrredundantSet","MaximalIndependentEdgeSet","MaximumIndependentEdgeSetCount","MaximumIndependentEdgeSets","MaximumIndependentVertexSetCount","MaximumNullity","MetricDimension","MinimumConnectedDominatingSet","MinimumCoveringsByMaximalCliques","MinimumCyclicEdgeCuts","MinimumDominatingSets","MinimumEdgeCuts","MinimumPathCoverings","MinimumTotalDominatingSets","MinimumVertexColorings","MinimumVertexCover","MinimumVertexCuts","MinimumWeightFractionalColoring","Minors","OddChordlessCyclePolynomial","OddChordlessCycles","Perfect1Factorizations","QuadraticEmbeddingConstant","RandicEnergy","Skewness","SomborEnergy","SomborSpectralRadius","Thickness","TotalDominatingSets","TotalDominationPolynomial","Triameter","TuttePolynomial","VertexCuts","VisibilityPolynomial"}
]
]&@@@add;

Close[file]