Nut Graph

Author

Eric W. Weisstein
December 27, 2023

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

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

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

Definition

A nut graph is a graph of at least 2 vertices whose adjacency matrix has nullity 1 (i.e., rank n-1 where n is the order of the graph) and for which the non-trivial kernel vector does not contain a zero.

Sources

https://hog.grinvin.org/meta-directory/nut

[1] K. Coolsaet, P.W. Fowler and J. Goedgebeur, Generation and properties of of nut graphs, MATCH Commun. Math. Comput. Chem., 80(2):423-444, 2018.
[2] J.B. Gauci, T. Pisanski and I. Sciriha, Existence of regular nut graphs and the Fowler construction, arXiv preprint arXiv:1904.02229, 2019.
[3] P.W. Fowler, J.B. Gauci, J. Goedgebeur, T. Pisanski and I. Sciriha, Existence of regular nut graphs for degree at most 11, Discussiones Mathematicae Graph Theory, 40(2):533-557, 2020.

Figure

GraphicsGrid[Flatten[Partition[#,UpTo[5]]&/@Map[Show[GraphData[#]//StyleGraphs,PlotLabel->TextCell[Style[GraphData[#,"Name"],Directive[Opacity[1],Black,Italic,14,FontFamily->"Times"]],PageWidth->500/5,TextAlignment->Center]]&,
Table[GraphData["Nut",n],{n,7,8}],{2}],1],ImageSize->700,Dividers->{{Thick,{True},Thick},{Thick,Thick,{True},Thick}}]

Classes

GraphClassesThatAreClass["Nut"]

Intersection@@(GraphData[#,"Classes"]&/@GraphData["Nut"])

Table[GraphData[{"Antiprism",n},"Nut"],{n,3,25}]

Table[Mod[n,3]=!=0,{n,3,25}]

Table[Piecewise[{{True,Mod[n,3]>0},{False,Mod[n,3]==0}}],{n,3,25}]

Counts

https://hog.grinvin.org/meta-directory/nut#nut

(Not in OEIS as of Nov 1, 2022)

0, 0, 0, 0, 0, 0, 3, 13, 560, 12551, 2060490, 208147869, 96477266994

RecognizeGraph/@Import["https://hog.grinvin.org/data/nuts/general/Nuts_general_7v.g6.gz"]

Table[Count[ConnectedGraphs[n],_?NutGraphQ],{n,9}]//Timing

Table[Count[Graphs[n],_?NutGraphQ],{n,9}]//Timing

Length/@Table[Select[GraphData/@GraphData[n],NutGraphQ],{n,20}]

Length/@Table[GraphData["Nut",n],{n,8}]

Parametrized families

<<MathWorld`Graphs`

Alkane

Table[GraphData[{"Alkane",n},"Nut"],{n,10}]

AlternatingGroupGraph

Table[GraphData[{"AlternatingGroupGraph",n},"Nut"],{n,2,6}]

Do[Print[{GraphData[{"AlternatingGroupGraph",n},"#"],NutGraphQ@GraphData[{"AlternatingGroupGraph",n}]//Timing}],{n,2,6}]

Andrasfai

Table[GraphData[{"Andrasfai",n},"Nut"],{n,10}]

Do[Print[{GraphData[{"Andrasfai",n},"#"],NutGraphQ@GraphData[{"Andrasfai",n}]//Timing}],{n,10}]

Antelope n×n

Table[GraphData[{"Antelope",{n,n}},"Nut"],{n,15}]

Antiprism

Entity["Graph",{"Antiprism",n}]["Nut"]

Table[GraphData[{"Antiprism",n},"Nut"],{n,3,25}]

2+Position[%,False]//Flatten

Table[Piecewise[{{False,Mod[n,3]==0}},True],{n,3,25}]==Table[GraphData[{"Antiprism",n},"Nut"],{n,3,25}]

Do[Print[{GraphData[{"Antiprism",n},"#"],NutGraphQ@GraphData[{"Antiprism",n}]//Timing}],{n,3,25}]

Apollonian

Table[GraphData[{"Apollonian",n},"Nut"],{n,5}]

Do[Print[{GraphData[{"Apollonian",n},"#"],NutGraphQ@GraphData[{"Apollonian",n}]//Timing}],{n,5}]

Barbell

Table[GraphData[{"Barbell",n},"Nut"],{n,3,20}]

Do[Print[{GraphData[{"Barbell",n},"#"],NutGraphQ@GraphData[{"Barbell",n}]//Timing}],{n,3,20}]

BlackBishop n×n

Table[GraphData[{"BlackBishop",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"BlackBishop",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Bishop",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Book

Table[GraphData[{"Book",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Book",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

Bruhat

Table[GraphData[{"Bruhat",n},"Nut"],{n,6}]

Do[Print[{gn=GraphData[{"Bruhat",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,6}]

Camel n×n

Table[GraphData[{"Camel",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Camel",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Centipede

Table[GraphData[{"Centipede",n},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Centipede",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

CocktailParty

Table[GraphData[{"CocktailParty",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"CocktailParty",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Complete

Entity["Graph",{"Complete",n}]["Nut"]

Table[GraphData[{"Complete",n},"Nut"],{n,30}]

Do[Print[{gn=GraphData[{"Complete",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["Nut"]

Flatten[Table[GraphData[{"CompleteBipartite",{m,n}},"Nut"],{n,20},{m,n}],1]//Union

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["Nut"]

Table[GraphData[{"CompleteBipartite",{n,n}},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"CompleteBipartite",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["Nut"]

Flatten[Table[GraphData[{"CompleteTripartite",{k,m,n}},"Nut"],{n,10},{m,n},{k,m}],2]//Union

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["Nut"]

Table[GraphData[{"CompleteTripartite",{n,n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"CompleteTripartite",{n,n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

CrossedPrism

Table[GraphData[{"CrossedPrism",2n},"Nut"],{n,2,10}]

Do[Print[{gn=GraphData[{"CrossedPrism",2n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Crown

Table[GraphData[{"Crown",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Crown",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["Nut"]

Table[GraphData[{"CubeConnectedCycle",n},"Nut"],{n,3,8}]

Do[Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["Nut"]

Table[GraphData[{"Cycle",n},"Nut"],{n,3,30}]

Do[Print[{gn=GraphData[{"Cycle",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,30}]

CycleComplement

Table[GraphData[{"CycleComplement",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"CycleComplement",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

DiagonalIntersection

Table[GraphData[{"DiagonalIntersection",n},"Nut"],{n,3,14}]

Do[Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,14}]

Dipyramid

Table[GraphData[{"Dipyramid",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Dipyramid",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Empty

Entity["Graph",{"Empty",n}]["Nut"]

Table[GraphData[{"Empty",n},"Nut"],{n,30}]

Do[Print[{gn=GraphData[{"Empty",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"Nut"],{n,15}]

Do[Print[{gn=GraphData[{"FibonacciCube",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,15}]

Flower

Table[GraphData[{"Flower",n},"Nut"],{n,5,20}]

Do[Print[{gn=GraphData[{"Flower",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,5,20}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"Nut"],{n,2,10}]

Do[Print[{gn=GraphData[{"FoldedCube",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Gear

Table[GraphData[{"Gear",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Gear",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

GeneralizedPetersen

Entity["Graph",{"GeneralizedPetersen",{n,k}}]["Nut"]

GraphData[#,"Nut"]&/@GraphData["GeneralizedPetersen"]//Union

Giraffe m×n

GraphData[#,"Nut"]&/@GraphData["Giraffe"]//Union

Giraffe n×n

Table[GraphData[{"Giraffe",{n,n}},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Giraffe",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

Goldberg

Table[GraphData[{"Goldberg",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Goldberg",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["Nut"]

GraphData[#,"Nut"]&/@Select[GraphData["Grid"],Length[GraphData[#,"NotationRules","Grid"]]==2&]//Union

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["Nut"]

Table[GraphData[{"Grid",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["Nut"]

GraphData[#,"Nut"]&/@Select[GraphData["Grid"],Length[GraphData[#,"NotationRules","Grid"]]==3&]//Union

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["Nut"]

Table[GraphData[{"Grid",{n,n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Grid",{n,n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

HalvedCube

Table[GraphData[{"HalvedCube",n},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"HalvedCube",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Hanoi

Table[GraphData[{"Hanoi",n},"Nut"],{n,5}]

Do[Print[{gn=GraphData[{"Hanoi",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,5}]

Harary

GraphData[#,"Nut"]&/@GraphData["Harary"]//Union

Helm

Table[GraphData[{"Helm",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Helm",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Hypercube

Entity["Graph",{"Hypercube",n}]["Nut"]

Table[GraphData[{"Hypercube",n},"Nut"],{n,0,10}]

Do[Print[{gn=GraphData[{"Hypercube",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["Nut"]

Table[GraphData[{"Keller",n},"Nut"],{n,5}]

Do[Print[{gn=GraphData[{"Keller",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,5}]

King m×n

GraphData[#,"Nut"]&/@GraphData["King"]

King n×n

Table[GraphData[{"King",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"King",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["Nut"]

GraphData[#,"Nut"]&/@GraphData["Knight"]//Union

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["Nut"]

Table[GraphData[{"Knight",{n,n}},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Knight",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

Ladder

Entity["Graph",{"Ladder",n}]["Nut"]

Table[GraphData[{"Ladder",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Ladder",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"Nut"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"Nut"],{n,3}]

Do[Print[{gn=GraphData[{"MengerSponge",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["Nut"]

Table[GraphData[{"MoebiusLadder",n},"Nut"],{n,3,25}]

Do[Print[{gn=GraphData[{"MoebiusLadder",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["Nut"]

Table[GraphData[{"Mycielski",n},"Nut"],{n,11}]

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,11}]

Odd

Entity["Graph",{"Odd",n}]["Nut"]

Table[GraphData[{"Odd",n},"Nut"],{n,7}]

Do[Print[{gn=GraphData[{"Odd",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,7}]

Pan

Table[GraphData[{"Pan",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Pan",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["Nut"]

Table[GraphData[{"Path",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Path",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

PathComplement

Table[GraphData[{"PathComplement",n},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"PathComplement",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["Nut"]

Table[GraphData[{"Prism",n},"Nut"],{n,3,25}]

Do[Print[{gn=GraphData[{"Prism",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,25}]

Queen m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Queen"],
Piecewise[{{True,Min[m,n]==1||(m==2&&n==3)||(m==2&&n==4)}},False],
GraphData[#,"Nut"]}&/@GraphData["Queen"],{_,x_,x_}]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Queen",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

Rook m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","Rook"],
Piecewise[{{True,Min[m,n]==1||m==n==2}},False],
GraphData[#,"Nut"]}&/@GraphData["Rook"],{_,x_,x_}]

Rook n×n

Table[GraphData[{"Rook",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"Rook",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

RookComplement m×n

DeleteCases[{
{m,n}=GraphData[#,"NotationRules","RookComplement"],
Piecewise[{{True,Min[m,n]<3}},False],
GraphData[#,"Nut"]}&/@GraphData["RookComplement"],{_,x_,x_}]

RookComplement n×n

Table[GraphData[{"RookComplement",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"RookComplement",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"Nut"],{n,4}]

Do[Print[{gn=GraphData[{"SierpinskiCarpet",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,4}]

SierpinskiGasket

Table[GraphData[{"SierpinskiGasket",n},"Nut"],{n,5}]

Do[Print[{gn=GraphData[{"SierpinskiGasket",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"Nut"],{n,6}]

Do[Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,4}]

StackedBook m×n

GraphData[#,"Nut"]&/@GraphData["StackedBook"]//Union

StackedBook n×n

Table[GraphData[{"StackedBook",{n,n}},"Nut"],{n,10}]

Do[Print[{gn=GraphData[{"StackedBook",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,10}]

StackedPrism m×n

GraphData[#,"Nut"]&/@GraphData["StackedPrism"]

StackedPrism n×n

Table[GraphData[{"StackedPrism",{n,n}},"Nut"],{n,3,5}]

Do[Print[{gn=GraphData[{"StackedPrism",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,5}]

Star

Entity["Graph",{"Star",n}]["Nut"]

Table[GraphData[{"Star",n},"Nut"],{n,25}]

Do[Print[{gn=GraphData[{"Star",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,25}]

Sun

Table[GraphData[{"Sun",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sun",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Sunlet

Table[GraphData[{"Sunlet",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Sunlet",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

TorusGrid m×n

GraphData[#,"Nut"]&/@GraphData["TorusGrid"]

TorusGrid n×n

Table[GraphData[{"TorusGrid",{n,n}},"Nut"],{n,3,10}]

Do[Print[{gn=GraphData[{"TorusGrid",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["Nut"]

Table[GraphData[{"Transposition",n},"Nut"],{n,6}]

Do[Print[{gn=GraphData[{"Transposition",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,6}]

Triangular

Table[GraphData[{"Triangular",n},"Nut"],{n,2,10}]

Do[Print[{gn=GraphData[{"Triangular",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,2,10}]

TriangularGrid

Table[GraphData[{"TriangularGrid",n},"Nut"],{n,0,10}]

Do[Print[{gn=GraphData[{"TriangularGrid",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,0,10}]

TriangularHoneycombAcuteKnight

Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"Nut"],{n,20}]

TriangularHoneycombBishop

Table[GraphData[{"TriangularHoneycombBishop",n},"Nut"],{n,9}]

TriangularHoneycombObtuseKnight

Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"Nut"],{n,20}]

TriangularHoneycombQueen

Table[GraphData[{"TriangularHoneycombQueen",n},"Nut"],{n,10}]

TriangularHoneycombRook

Table[GraphData[{"TriangularHoneycombRook",n},"Nut"],{n,10}]

TriangularSnake

Table[GraphData[{"TriangularSnake",n},"Nut"],{n,1,20,2}]

Do[Print[{gn=GraphData[{"TriangularSnake",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,1,20,2}]

Web

Table[GraphData[{"Web",n},"Nut"],{n,3,20}]

Do[Print[{gn=GraphData[{"Web",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,3,20}]

Wheel

Entity["Graph",{"Wheel",n}]["Nut"]

Table[GraphData[{"Wheel",n},"Nut"],{n,4,20}]

Do[Print[{gn=GraphData[{"Wheel",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WheelComplement

Table[GraphData[{"WheelComplement",n},"Nut"],{n,4,20}]

Do[Print[{gn=GraphData[{"WheelComplement",n},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,4,20}]

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"Nut"],{n,2,10}]

Do[Print[{gn=GraphData[{"WhiteBishop",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,2,10}]

Zebra m×n

GraphData[#,"Nut"]&/@GraphData["Zebra"]//Union

Zebra n×n

Table[GraphData[{"Zebra",{n,n}},"Nut"],{n,20}]

Do[Print[{gn=GraphData[{"Zebra",{n,n}},"#"],NutGraphQ@GraphData[gn]//Timing}],{n,20}]

Circulant nut graphs

Sources

https://arxiv.org/abs/2212.03026v1

Complete resolution of the circulant nut graph order–degree existence problem
Ivan Damnjanovic
December 7, 2022

we will use N_d to denote the set of all the orders that a d-regular circulant nut graph can have, for each d ∈ N_0

CirculantNutGraphQ[n_,d_]:=Or[
(Mod[n,2]==0&&n≥d+4)&&Mod[d,8]==4,
(n==14||(Mod[n,2]==0&&n≥18))&&d==8,
(Mod[n,2]==0&&n≥d+6)&&(Mod[d,8]==0&&d≥16)
]

theoremallowed=Cases[Flatten[Table[{n,d,CirculantNutGraphQ[n,d]},{n,20},{d,n}],1],{i__,True}:>{i}]

Examples

circnuts=GraphData[{"Circulant","Nut"}]

Δ = 2 * (number of indices)

DeleteCases[{GraphData[#,"MaximumVertexDegree"],2Length[GraphData[#,"NotationRules","Circulant"][[2]]]}&/@circnuts,{x_,x_}]

graphs={#,2Length[#2]}&@@@(GraphData[#,"NotationRules","Circulant"]&/@circnuts)

Union[graphs]

allowedgraphs=Cases[graphs,{_?(#≤20&),_}]//Union

theoremallowed===allowedgraphs

Figure

circnuts=SortBy[GraphData[{"Circulant","Nut"},;;16],GraphData[#,"V"]&]

GraphicsGrid[Map[StyleGraphs[Annotate[GraphData[#,"Graph","Circulant"][[1]],{PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Italic,Black,FontFamily->"Times"]}]]&,SplitBy[circnuts,GraphData[#,"V"]&],{2}],ImageSize->700,Dividers->All]

Embeddings

<<MathWorld`Graphs`

{"Nut", {7, 1}} == {"Matchstick", {8, 71}}

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

{"Nut", {7, 2}}

GraphData[{"Nut",{7,2}},"StandardName"]

Primary

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

All

GraphData[{"Nut",{7,2}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{7,2}},"EdgeList"]]

Triangle embedding

RegionDistance[Line[v[[{1,2}]]],{0,0}]

v=Join[UnitCirclePoints[3],{{0,0}},CirclePoints[{(1/(4 (Sqrt[3]))),-Pi/2},3]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,4,3,7,4,2,6,4,5,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Default embedding

GraphPlot@GraphData[{"Nut",{7,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{7,2}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{7,2}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Nut",{7,2}},"Planar"]

GraphData[{"Nut",{7,2}},"Graph","Planar"]//StyleGraphs

Planar embedding

GraphPlot@PlanarGraph[GraphData[{"Nut",{7,2}},"Edges"]]

Circulant

GraphData[{"Nut",{7,2}},"Circulant"]

GraphData[{"Nut",{7,2}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{7,2}},"Halin"]

GraphData[{"Nut",{7,2}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{7,2}},"LCF"]

GraphData[{"Nut",{7,2}},"LCFSignature"]

GraphData[{"Nut",{7,2}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{7,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{7,2}}],Debug->True]//Timing

GraphData[{"Nut",{7,2}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{7,2}},"Matchstick"]

GraphData[{"Nut",{7,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{7,2}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Nut",{7,2}},"Polyhedral"]

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

{"Nut", {7, 3}}

GraphData[{"Nut",{7,3}},"StandardName"]

Primary

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

All

GraphData[{"Nut",{7,3}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{7,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{7,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{7,3}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{7,3}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Nut",{7,3}},"Planar"]

GraphData[{"Nut",{7,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{7,3}},{"RCN","CN"}]

GraphData[{"Nut",{7,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{7,3}}],"CrossingNumber"->cn]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{7,3}},"Circulant"]

GraphData[{"Nut",{7,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{7,3}},"Halin"]

GraphData[{"Nut",{7,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{7,3}},"LCF"]

GraphData[{"Nut",{7,3}},"LCFSignature"]

GraphData[{"Nut",{7,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{7,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{7,3}}],Debug->True]//Timing

GraphData[{"Nut",{7,3}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{7,3}},"Matchstick"]

GraphData[{"Nut",{7,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{7,3}},"Edges"]]

3D All

GraphData[{"Nut",{7,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{7,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{7,3}},"Polyhedral"]

GraphData[{"Nut",{7,3}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 1}}

Names

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

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

Primary

GraphData[{"Nut",{8,1}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,1}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,1}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"Nut",{8,1}},"Edges"],Pi]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,1}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{8,1}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Nut",{8,1}},"Planar"]

GraphData[{"Nut",{8,1}},"Graph","Planar"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,1}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"Nut",{8,1}}],TimeConstraint->60]//AbsoluteTiming

GraphPlot[GraphData[{"Nut",{8,1}},"Edges"],GraphLayout->"TutteEmbedding"]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"Nut",{8,1}},"Edges"],GraphLayout->"TutteEmbedding"]

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

RecognizeGraph[g]

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,1}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,1}},"Circulant"]

GraphData[{"Nut",{8,1}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,1}},"Halin"]

GraphData[{"Nut",{8,1}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,1}},"LCF"]

GraphData[{"Nut",{8,1}},"LCFSignature"]

GraphData[{"Nut",{8,1}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,1}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,1}}],Debug->True]//Timing

GraphData[{"Nut",{8,1}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Nut",{8,1}},"VertexList"],GraphData[{"Nut",{8,1}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Nut",{8,1}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Nut",{8,1}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Nut",{8,1}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance construction

LabelGraph@

RecognizeGraph@VertexDelete[%,{3,4}]

GraphData[{"Matchstick",{8,23}},"Graph","All"]

GraphData[{"Matchstick",{8,23}},"Graph",{"Labeled","UnitDistance"}]

UnitDistancePoint[v[[1]],v[[4]],1]

v=GraphEmbedding@GraphData[{"Matchstick",{8,23}},"Graph",{"Labeled","UnitDistance"}][[1]];
v=Join[v,{UnitDistancePoint[v[[1]],v[[4]]],UnitDistancePoint[v[[2]],v[[6]]]}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[3,5,2,6,1,3],e[1,7,4,1],e[2,4,6,8,2]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

{{"Nut",{8,1}},l=FindSubgraphUnitDistanceEmbedding[GraphData[{"Nut",{8,1}}];Graphs[8][[7122]],TimeConstraint->300,"Results"->All]//Timing}

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

gs={,,};

Matchstick

GraphData[{"Nut",{8,1}},"M"]

GraphData[{"Nut",{8,1}},"Matchstick"]

GraphData[{"Nut",{8,1}},"Graph","Matchstick"]//StyleGraphs

Matchstick (non-)construction

GraphData[{"Nut",{8,1}},"Graph","UnitDistance"]//StyleGraphs

Since the line of 4 triangles is rigid, any chain of 3 edges from top left to bottom right cannot go around the existing corners, so the graph cannot be matchstick

3D default

Graph3D[GraphData[{"Nut",{8,1}},"Edges"]]

3D All

GraphData[{"Nut",{8,1}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,1}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,1}},"Polyhedral"]

GraphData[{"Nut",{8,1}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 2}}

GraphData[{"Nut",{8,2}},"StandardName"]

Primary

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

All

GraphData[{"Nut",{8,2}},"Graph","All"]//StyleGraphs

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,2}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,2}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,2}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,2}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,2}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,2}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,2}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Nut",{8,2}},"Planar"]

GraphData[{"Nut",{8,2}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,2}},{"RCN","CN"}]

GraphData[{"Nut",{8,2}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

CrossingNumber[GraphData[{"Nut",{8,2}}],TimeConstraint->60]//AbsoluteTiming

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

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,2}}],"CrossingNumber"->cn]]

GraphPlot@

GraphPlot@HighlightGraph[RotateGraph[GraphicsToGraph@,Pi],9]

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

RecognizeGraph[g]

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,2}},"Circulant"]

GraphData[{"Nut",{8,2}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,2}},"Halin"]

GraphData[{"Nut",{8,2}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,2}},"LCF"]

GraphData[{"Nut",{8,2}},"LCFSignature"]

GraphData[{"Nut",{8,2}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,2}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,2}}],Debug->True]//Timing

GraphData[{"Nut",{8,2}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,2}},"Matchstick"]

GraphData[{"Nut",{8,2}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,2}},"Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData[{"Nut",{8,2}},"Polyhedral"]

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

{"Nut", {8, 3}}

GraphData[{"Nut",{8,3}},"StandardName"]

Primary

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

All

GraphData[{"Nut",{8,3}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,3}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,3}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,3}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{8,3}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,3}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,3}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Nut",{8,3}},"Planar"]

GraphData[{"Nut",{8,3}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,3}},{"RCN","CN"}]

GraphData[{"Nut",{8,3}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

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

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,3}}],"CrossingNumber"->cn]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,3}},"Circulant"]

GraphData[{"Nut",{8,3}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,3}},"Halin"]

GraphData[{"Nut",{8,3}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,3}},"LCF"]

GraphData[{"Nut",{8,3}},"LCFSignature"]

GraphData[{"Nut",{8,3}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,3}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,3}}],Debug->True]//Timing

GraphData[{"Nut",{8,3}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,3}},"Matchstick"]

GraphData[{"Nut",{8,3}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,3}},"Edges"]]

3D All

GraphData[{"Nut",{8,3}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,3}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,3}},"Polyhedral"]

GraphData[{"Nut",{8,3}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 4}}

GraphData[{"Nut",{8,4}},"StandardName"]

Primary

GraphData[{"Nut",{8,4}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,4}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,4}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,4}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,4}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{8,4}},"Hamiltonian"]

GraphData[{"Nut",{8,4}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Nut",{8,4}},"Planar"]

GraphData[{"Nut",{8,4}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,4}},{"RCN","CN"}]

GraphData[{"Nut",{8,4}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,4}}],TimeConstraint->10])//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,4}}],"CrossingNumber"->cn]]

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,4}},"Circulant"]

GraphData[{"Nut",{8,4}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,4}},"Halin"]

GraphData[{"Nut",{8,4}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,4}},"LCF"]

GraphData[{"Nut",{8,4}},"LCFSignature"]

GraphData[{"Nut",{8,4}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,4}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,4}}],Debug->True]//Timing

GraphData[{"Nut",{8,4}},"Graph","UnitDistance"]//StyleGraphs

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData[{"Nut",{8,4}},"VertexList"],GraphData[{"Nut",{8,4}},"EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

UnitDistanceEmbeddingRefine/@GraphData[{"Nut",{8,4}},"Graph","All"]

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistanceEmbeddingRefine/@Complement@@(GraphData[{"Nut",{8,4}},"Graph",#]&/@{"All","UnitDistance"})

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

FindUnitDistanceEmbedding[GraphData[{"Nut",{8,4}}],MaxIterations->5000,"ReturnWithMessage"->True]//Timing

FindUnitDistanceEmbedding[GraphData[{"Nut",{8,4}}],MaxIterations->5000,"ReturnWithMessage"->False]//Quiet//Timing

FindUnitDistanceEmbedding[GraphData[{"Nut",{8,4}}],MaxIterations->50000,"ReturnWithMessage"->False]//Quiet//Timing

UnitDistance by FindSubgraphUnitDistanceEmbedding

GraphData[{"Nut",{8,4}},"StandardNames"]

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

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

gs={TranslateGraph[RotateGraph[LabelGraph@,{156,20}],23],}

Matchstick

GraphData[{"Nut",{8,4}},"Matchstick"]

GraphData[{"Nut",{8,4}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,4}},"Edges"]]

3D All

GraphData[{"Nut",{8,4}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,4}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,4}},"Polyhedral"]

GraphData[{"Nut",{8,4}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 5}}

GraphData[{"Nut",{8,5}},"StandardName"]

Primary

GraphData[{"Nut",{8,5}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,5}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,5}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,5}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,5}},"Graph","Degenerate"]//StyleGraphs

Circular

GraphData[{"Nut",{8,5}},"Graph","Circular"]//StyleGraphs

Planar

GraphData[{"Nut",{8,5}},"Planar"]

GraphData[{"Nut",{8,5}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,5}},{"RCN","CN"}]

GraphData[{"Nut",{8,5}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,5}}],TimeConstraint->10])//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,5}}],"CrossingNumber"->cn],Pi/4]

Mean[v[[{2,7}]]]

v={{0,0},{1,0},{1,1},{0,1},{1/2,3/4},{3/4,3/4},{5/8+1/16,1/2+1/4-1/8},{(27/32),(5/16)}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1],e[4,2,6,3,5,6,8,5,4],e[5,2,8,7,5]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,5}},"Circulant"]

GraphData[{"Nut",{8,5}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,5}},"Halin"]

GraphData[{"Nut",{8,5}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,5}},"LCF"]

GraphData[{"Nut",{8,5}},"LCFSignature"]

GraphData[{"Nut",{8,5}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,5}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,5}}],Debug->True]//Timing

GraphData[{"Nut",{8,5}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,5}},"Matchstick"]

GraphData[{"Nut",{8,5}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,5}},"Edges"]]

3D All

GraphData[{"Nut",{8,5}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,5}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,5}},"Polyhedral"]

GraphData[{"Nut",{8,5}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 6}}

GraphData[{"Nut",{8,6}},"StandardName"]

Primary

GraphData[{"Nut",{8,6}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,6}},"Graph","All"]//StyleGraphs

Inexact

Select[GraphData[{"Nut",{8,6}},"Graph","All"],(!FreeQ[GraphEmbedding[#],_?InexactNumberQ]&)]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,6}},"EdgeList"]]

Default embedding

GraphPlot[GraphData[{"Nut",{8,6}},"Edges"],GraphLayout->"LayeredEmbedding"]

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

GraphPlot@GraphData[{"Nut",{8,6}},"Edges"]

GraphPlot@RotateGraph[GraphicsToGraph@,-Pi/2]

v={{0,0},{1,0},{1,1},{1/2,1},{0,1},{1/2,1/2},{1/2,3/2}};
AppendTo[v,Mean[v[[{4,7,5}]]]];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,1,6,2,4,1],e[5,7,3],e[4,8,7,4],e[5,6,3]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,6}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,6}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,6}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,6}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,6}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Nut",{8,6}},"Planar"]

GraphData[{"Nut",{8,6}},"Graph","Planar"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,6}}],TimeConstraint->10])//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,6}}],"CrossingNumber"->cn]]

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

GraphPlot@RotateGraph[,Pi/4]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,6}},"Circulant"]

GraphData[{"Nut",{8,6}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,6}},"Halin"]

GraphData[{"Nut",{8,6}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,6}},"LCF"]

GraphData[{"Nut",{8,6}},"LCFSignature"]

GraphData[{"Nut",{8,6}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,6}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,6}}],Debug->True]//Timing

GraphData[{"Nut",{8,6}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,6}},"Matchstick"]

GraphData[{"Nut",{8,6}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,6}},"Edges"]]

3D All

GraphData[{"Nut",{8,6}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,6}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,6}},"Polyhedral"]

GraphData[{"Nut",{8,6}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 7}}

GraphData[{"Nut",{8,7}},"StandardName"]

Primary

GraphData[{"Nut",{8,7}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,7}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,7}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,7}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,7}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,7}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,7}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,7}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,7}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Nut",{8,7}},"Planar"]

GraphData[{"Nut",{8,7}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,7}},{"RCN","CN"}]

GraphData[{"Nut",{8,7}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,7}}],TimeConstraint->10])//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,7}}],"CrossingNumber"->cn]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

Cases[GraphData[{"Nut",{8,7}},"StandardNames"],{"Circulant",_}]

GraphData[{"Nut",{8,7}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,7}},"Halin"]

GraphData[{"Nut",{8,7}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,7}},"LCF"]

GraphData[{"Nut",{8,7}},"LCFSignature"]

GraphData[{"Nut",{8,7}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,7}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,7}}],Debug->True]//Timing

GraphData[{"Nut",{8,7}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,7}},"Matchstick"]

GraphData[{"Nut",{8,7}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,7}},"Edges"]]

3D All

GraphData[{"Nut",{8,7}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,7}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,7}},"Polyhedral"]

GraphData[{"Nut",{8,7}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 8}} == {"Octahedral", 124}

GraphData[{"Nut",{8,8}},"StandardName"]

{"Nut", {8, 9}}

GraphData[{"Nut",{8,9}},"StandardName"]

Primary

GraphData[{"Nut",{8,9}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,9}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,9}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,9}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,9}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,9}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,9}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,9}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,9}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

Planar

GraphData[{"Nut",{8,9}},"Planar"]

GraphData[{"Nut",{8,9}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,9}},{"RCN","CN"}]

GraphData[{"Nut",{8,9}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,9}}],TimeConstraint->10])//AbsoluteTiming

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,9}}],"CrossingNumber"->cn]]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,9}},"Circulant"]

GraphData[{"Nut",{8,9}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,9}},"Halin"]

GraphData[{"Nut",{8,9}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,9}},"LCF"]

GraphData[{"Nut",{8,9}},"LCFSignature"]

GraphData[{"Nut",{8,9}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,9}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,9}}],Debug->True]//Timing

GraphData[{"Nut",{8,9}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,9}},"Matchstick"]

GraphData[{"Nut",{8,9}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,9}},"Edges"]]

3D All

GraphData[{"Nut",{8,9}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,9}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,9}},"Polyhedral"]

GraphData[{"Nut",{8,9}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 10}}

GraphData[{"Nut",{8,10}},"StandardName"]

Primary

GraphData[{"Nut",{8,10}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,10}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,10}},"EdgeList"]]

Default embedding

GraphPlot@GraphData[{"Nut",{8,10}},"Edges"]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,10}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,10}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,10}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,10}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,10}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

quad

Planar

GraphData[{"Nut",{8,10}},"Planar"]

GraphData[{"Nut",{8,10}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,10}},{"RCN","CN"}]

GraphData[{"Nut",{8,10}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,10}}],TimeConstraint->10])//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,10}}],"CrossingNumber"->cn],-Pi/4]

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

GraphPlot@

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,10}},"Circulant"]

GraphData[{"Nut",{8,10}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,10}},"Halin"]

GraphData[{"Nut",{8,10}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,10}},"LCF"]

GraphData[{"Nut",{8,10}},"LCFSignature"]

GraphData[{"Nut",{8,10}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,10}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,10}}],Debug->True]//Timing

GraphData[{"Nut",{8,10}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,10}},"Matchstick"]

GraphData[{"Nut",{8,10}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,10}},"Edges"]]

3D All

GraphData[{"Nut",{8,10}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,10}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,10}},"Polyhedral"]

GraphData[{"Nut",{8,10}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 11}}

GraphData[{"Nut",{8,11}},"StandardName"]

Primary

GraphData[{"Nut",{8,11}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,11}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,11}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"Nut",{8,11}},"Edges"],-Pi/2]

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

RecognizeGraph[g]

Degenerate

GraphData[{"Nut",{8,11}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,11}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,11}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,11}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,11}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

Planar

GraphData[{"Nut",{8,11}},"Planar"]

GraphData[{"Nut",{8,11}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,11}},{"RCN","CN"}]

GraphData[{"Nut",{8,11}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,11}}],TimeConstraint->10])//AbsoluteTiming

CrossingNumber[GraphData[{"Nut",{8,11}}],TimeConstraint->60]//AbsoluteTiming

g=RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,11}}],"CrossingNumber"->cn]]

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

GraphPlot@RotateGraph[,-Pi/4]

v={{0,0},{1,0},{1,1},{0,1},{1/2,1/2},{3/4,1/2},{1/2,1/4},{9/16,6/16}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,1,7,2,6,4,7,6,3,5,1],e[7,5,6,8,7],e[8,5,4,8]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData[{"Nut",{8,11}},"Circulant"]

GraphData[{"Nut",{8,11}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,11}},"Halin"]

GraphData[{"Nut",{8,11}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,11}},"LCF"]

GraphData[{"Nut",{8,11}},"LCFSignature"]

GraphData[{"Nut",{8,11}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,11}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,11}}],Debug->True]//Timing

GraphData[{"Nut",{8,11}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,11}},"Matchstick"]

GraphData[{"Nut",{8,11}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,11}},"Edges"]]

3D All

GraphData[{"Nut",{8,11}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,11}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,11}},"Polyhedral"]

GraphData[{"Nut",{8,11}},"Graph",{"3D","Polyhedron"}]

{"Nut", {8, 12}} == {"Antiprism", 4}

GraphData[{"Nut",{8,12}},"StandardName"]

{"Nut", {8, 13}}

GraphData[{"Nut",{8,13}},"StandardName"]

Primary

GraphData[{"Nut",{8,13}}]//StyleGraphs[#,ImageSize->Small]&

All

GraphData[{"Nut",{8,13}},"Graph","All"]//StyleGraphs

Embedding types

GraphDataEmbeddings[GraphData[{"Nut",{8,13}},"EdgeList"]]

Default embedding

GraphPlot@RotateGraph[Graph@GraphData[{"Nut",{8,13}},"Edges"],-Pi/2]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

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

RecognizeGraph[g]

GraphPlot[GraphData[{"Nut",{8,13}},"Edges"],GraphLayout->"HighDimensionalEmbedding"]

GraphPlot@RotateGraph[GraphicsToGraph@,Pi/2]

v=Join[UnitCirclePoints[6,-Pi/2],{#/3,0}&/@{-1,1}];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,4,5,6,1,7,8,1],e[5,3,7,6,4,2,8,5,7,2],e[6,8,3]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

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

Degenerate

GraphData[{"Nut",{8,13}},"Graph","Degenerate"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,13}},"Graph","Bilateral"]//StyleGraphs

Bilateral

GraphData[{"Nut",{8,13}},"Graph","Bilateral"]//StyleGraphs

Circular

GraphData[{"Nut",{8,13}},"Graph","Circular"]//StyleGraphs

Circular construction

Length[hc=FindHamiltonianCycle[GraphData[{"Nut",{8,13}}],All][[All,All,1]]]

Length[bilat=DeleteDuplicatesBy[
DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData[{"Nut",{8,13}}],#]&/@hc],
CircularCanonicalGraphEmbedding]]//Timing

gs=bilat

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

Planar

GraphData[{"Nut",{8,13}},"Planar"]

GraphData[{"Nut",{8,13}},"Graph","Planar"]//StyleGraphs

MinimalCrossing

GraphData[{"Nut",{8,13}},{"RCN","CN"}]

GraphData[{"Nut",{8,13}},"Graph","MinimalCrossing"]//StyleGraphs

MinimalCrossing construction

(cn=CrossingNumber[GraphData[{"Nut",{8,13}}],TimeConstraint->10])//AbsoluteTiming

Table[MinimalCrossingGraph[GraphData[{"Nut",{8,13}}],"CrossingNumber"->3,RandomSeed->n],{n,5000}]//Union//Timing

RecognizeGraph[g]

RectilinearCrossingCount[g]

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

Union[Select[Table[RotateGraph[MinimalCrossingGraph[GraphData[{"Nut",{8,13}}],"CrossingNumber"->cn,RandomSeed->n]],{n,2000}],Max[OuterFace[#]]<=GraphData[{"Nut",{8,13}},"V"]-1&]]//Timing

GraphPlot@MinimalCrossingGraph[GraphData[{"Nut",{8,13}}],"CrossingNumber"->4]

SelectFirst[Table[GraphPlot[GraphData[{"Nut",{8,13}},"Edges"],GraphLayout->"RandomEmbedding"],{10000}],RectilinearCrossingCount[#]==3&]//Timing

SelectFirst[Table[GraphPlot[GraphData[{"Nut",{8,13}},"Edges"],GraphLayout->"RandomEmbedding"],{10^5}],RectilinearCrossingCount[#]==3&]//Timing

Length[gs=Select[Table[GraphPlot[GraphData[{"Nut",{8,13}},"Edges"],GraphLayout->"RandomEmbedding"],{10000}],RectilinearCrossingCount[#]<6&]]//Timing

GraphPlot@GraphData[{"Nut",{8,13}},"Edges"]

GraphicsToGraph@

RectilinearCrossingCount@%

v=Join[UnitCirclePoints[3],CirclePoints[{1/5,-Pi/2},3],{{0,0}}];
AppendTo[v,v[[4]]+(v[[5]]-v[[4]])/4];
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,1,5,2,6,3,4,1,7,4,8,5,6,4],e[3,7,5],e[2,7,8,1]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph@g

RectilinearCrossingCount@g

Circulant

GraphData[{"Nut",{8,13}},"Circulant"]

GraphData[{"Nut",{8,13}},"Graph","Circulant"]//StyleGraphs

Halin

GraphData[{"Nut",{8,13}},"Halin"]

GraphData[{"Nut",{8,13}},"Graph","Halin"]//StyleGraphs

LCF

GraphData[{"Nut",{8,13}},"LCF"]

GraphData[{"Nut",{8,13}},"LCFSignature"]

GraphData[{"Nut",{8,13}},"Graph","LCF"]//StyleGraphs

UnitDistance

GraphData[{"Nut",{8,13}},"UnitDistance"]

UnitDistanceGraphQ[GraphData[{"Nut",{8,13}}],Debug->True]//Timing

GraphData[{"Nut",{8,13}},"Graph","UnitDistance"]//StyleGraphs

Matchstick

GraphData[{"Nut",{8,13}},"Matchstick"]

GraphData[{"Nut",{8,13}},"Graph","Matchstick"]//StyleGraphs

3D default

Graph3D[GraphData[{"Nut",{8,13}},"Edges"]]

3D All

GraphData[{"Nut",{8,13}},"Graph",{"3D","All"}]

3D UnitDistance

GraphData[{"Nut",{8,13}},"Graph",{"3D","UnitDistance"}]

3D Polyhedron

GraphData[{"Nut",{8,13}},"Polyhedral"]

GraphData[{"Nut",{8,13}},"Graph",{"3D","Polyhedron"}]

GraphData

nut7=MapIndexed[{#,RecognizeGraph[#],#2[[1]]}&,Import["https://hog.grinvin.org/data/nuts/general/Nuts_general_7v.g6.gz"]]

l={#2,{0,Union[GraphData[#2,"NotationRules"],{"Nut"->{7,#3}}]}}&@@@nut7

GetGraphData[{"Matchstick",{8,71}},"File"]

nut8=MapIndexed[{#,RecognizeGraph[#,"Cache"->"InternalOnly"],#2[[1]]}&,Import["https://hog.grinvin.org/data/nuts/general/Nuts_general_8v.g6.gz"]]

l={#2,{0,Union[GraphData[#2,"NotationRules"],{"Nut"->{8,#3}}]}}&@@@DeleteCases[nut8,{_,{"Nut",_},_}]

PropertyReplace[l,"NotationRules","13.3"]

RenameGraphFiles[]

l={#2,{0,SortBy[Append[GraphData[#2,"AlternateStandardNames"],{"Nut",{8,#3}}],First[Flatten[{#}]]&]}}&@@@DeleteCases[nut8,{_,{"Nut",_},_}]

PropertyReplace[l,"AlternateStandardNames","13.3"]

RenameGraphFiles[]

l={#2,{0,Union[GraphData[#2,"AlternateNames"],{"8\[Hyphen]nut graph "<>ToString[#3]}]}}&@@@DeleteCases[nut8,{_,{"Nut",_},_}]

PropertyReplace[l,"AlternateNames","13.3"]

RenameGraphFiles[]

new=Cases[nut8,{g_,{},i_}:>{g,i}]

file=OpenWrite["~/nut.m"]

WriteString[file,GraphDataString[#,
"StandardName"->{"Nut",{8,#2}},
"Name"->"8\[Hyphen]nut graph "<>ToString[#2],
"Embeddings"->None,
"NotationRules"->{"Nut"->{8,#2}},
"Information"->"NutGraph"
]]&@@@new