Exoo-Ismailescu Graphs

Author

Eric W. Weisstein
April 25, 2024

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/Exoo-IsmailescuGraphs.nb.

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

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

Smallest triangle-free UD graphs with χ == 4 and girth 4

Soifer 2008, p. 445

Soifer 2024, p. 145

Exoo-Ismailescu 17-, 19-, and 21-node graphs are smaller

UnitDistance

Grid[Sort[GraphData[#,{"V","#"}]&/@Select[GraphData[{"UnitDistance","TriangleFree"}],GraphData[#,"ChromaticNumber"]===4&&GraphData[#,"Girth"]==4&]],Dividers->All,Alignment->Left]

All

Grid[Sort[GraphData[#,{"V","#"}]&/@Select[GraphData["TriangleFree"],GraphData[#,"ChromaticNumber"]===4&&GraphData[#,"Girth"]==4&]],Dividers->All,Alignment->{{Decimal,Left}}]

Figures

exoo=SortBy[GraphData["ExooIsmailescuGraph*"],GraphData[#,"V"]&]

GraphicsGrid[Partition[Show[GraphData[#]//StyleGraphs,PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Black,Italic,FontFamily->"Times"]]&/@SortBy[GraphData["ExooIsmailescuGraph"~~DigitCharacter ..],GraphData[#,"V"]&],UpTo[4]],Dividers->All,Alignment->Top,ImageSize->1000]

Small triangle-free unit-distance graphs with chromatic number 4 and girth 4

Exoo, G. and Ismailescu, D.  "Small Order Triangle-Free 4-Chromatic Unit Distance Graphs.''  Geombinatorics 26, No. 2, 49–64, 2016.

exoo1={"ExooIsmailescuGraph17","ExooIsmailescuGraph19","ExooIsmailescuGraph21"};

TextGrid[GraphData[#,{"#","UnitDistance","ChromaticNumber","Girth"}]&/@exoo1,Dividers->All]

GraphicsRow[Show[GraphData[#]//StyleGraphs,PlotLabel->GraphData[#,"Name"]]&/@{"ExooIsmailescuGraph17","ExooIsmailescuGraph19","ExooIsmailescuGraph21"},BaseStyle->InsetBoxOptions->{BaseStyle->Directive[Black,Italic,FontFamily->"Times",14]},Dividers->All]

Unit-distance girth 3

Exoo, G. and Ismailescu, D.  "The Chromatic Number of the Plane Is at Least 5—A New Proof."  1 May 2018.  https://arxiv.org/abs/1805.00157

exoo2=Table["ExooIsmailescuGraph"<>ToString[n],{n,{40,49,51,79, 627}}]

TextGrid[GraphData[#,{"#","UnitDistance","ChromaticNumber","Girth"}]&/@exoo2,Dividers->All]

GraphicsRow[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.02}],PlotLabel->GraphData[#,"Name"]]&/@Table["ExooIsmailescuGraph"<>ToString[n],{n,{40,49,51,79, 627}}],BaseStyle->InsetBoxOptions->{BaseStyle->Directive[Black,Italic,FontFamily->"Times",14]},Dividers->All,ImageSize->1000]

XXX

Exoo, G. and Ismailescu, D.  "A 6-Chromatic Two-Distance Graph in the Plane."  29 Sep 2019.  https://arxiv.org/abs/1909.13177

exoo3={"ExooIsmailescuGraph205","ExooIsmailescuGraph214"};

TextGrid[GraphData[#,{"#","UnitDistance","ChromaticNumber","Girth"}]&/@exoo3,Dividers->All]

GraphicsRow[Show[StyleGraphs[GraphData[#],VertexSize->{"Scaled",.015}],PlotLabel->GraphData[#,"Name"]]&/@{"ExooIsmailescuGraph205","ExooIsmailescuGraph214"},BaseStyle->InsetBoxOptions->{BaseStyle->Directive[Black,Italic,FontFamily->"Times",14]},Dividers->All]

"ExooIsmailescuGraph17"

Embeddings from
Exoo, G. and Ismailescu, D.  "Small order triangle-free 4-chromatic unit distance graphs."  Geombinatorics 26, no. 2, 49–64, 2016.

Primary

GraphData["ExooIsmailescuGraph17"]//StyleGraphs

All

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

UnitDistance

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

Coloring

With[{gn="ExooIsmailescuGraph17"},GraphicsRow[GraphData[gn,"Graph","All"]/.g_System`Graph:>SetProperty[g,{
System`VertexStyle->MapIndexed[#2[[1]]->{Red,Yellow,Green,Blue}[[#]]&,GraphData[gn,"MinimumVertexColoring"]],
VertexSize->Large}],ImageSize->Large]]

GraphData["ExooIsmailescuGraph","UnitDistance"]

GraphData["ExooIsmailescuGraph","Girth"]

GraphData["ExooIsmailescuGraph","CyclePolynomial"][x]

GraphData["ExooIsmailescuGraph","TriangleFree"]

Minimal CN embedding

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

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

Default embedding

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

v={{0,0},{3,0},{6,0},{2,1},{4,1},{0,1},{1,1},{2,2},{4,2},{5,1},{6,1},{2,3},{4,3},{0,4},{1,4},{5,4},{6,4}};
g=Graph[Range[Length[v]],UndirectedEdge@@@{e[1,2,3,11,17,16,15,14,6,1,4,5,3],e[12,6,7,15,13,12,16,10,11,13],e[7,4,8,12],e[10,5,9,13],e[14,8,2,9,17]},VertexCoordinates->v,VertexLabels->Automatic]

RecognizeGraph[g]

MinimalCrossing Construction

GraphPlot@RotateGraph[MinimalCrossingGraph[GraphData["ExooIsmailescuGraph17"],"CrossingNumber"->5],-Pi/2]

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Original paper [12 embeddings modulo symmetry]

Soifer 2008

Soifer 2024, pp. 158–169:

Equations in z

Lousy:

TextRecognize[]

Lousy:

Import["/Users/eww/Documents/Books/Solifer2024.pdf",{"PagePlaintext",191}]

Import["/Users/eww/Documents/Books/Solifer2024.pdf",{"FormattedText",191}]

Lousy:

Import["/Users/eww/Documents/Books/Solifer2024.pdf",{"PageGraphics",191}]

gg=Graph[UndirectedEdge@@@{{1,8},{1,12},{1,15},{2,9},{2,10},{2,16},{3,9},{3,15},{3,16},{3,17},{4,10},{4,11},{4,16},{5,11},{5,13},{5,16},{6,12},{6,13},{6,14},{7,12},{7,14},{7,15},{8,13},{8,14},{8,17},{9,11},{9,13}, {10,15},{10,17},{11,14},{12,17}}]

RecognizeGraph@%

cyc=FindCycle[gg,4,All][[All,All,1]]

Union[Flatten[cyc]]

Clear[z]

eqn=#1+#2-#3-#4=={0,0}&@@@Map[z,cyc,{2}]

eqn2=(Join[eqn,
{z[17]=={0,0},z[3]=={1,0},z[8]==z[17]+(({(a^2)-1,2a})/((a^2)+1)),z[10]==z[17]+(({(b^2)-1,2b})/((b^2)+1)),z[9]==z[3]+(({(c^2)-1,2c})/((c^2)+1)),z[14]==z[8]+(({(d^2)-1,2d})/((d^2)+1)),z[16]==z[3]+(({(e^2)-1,2e})/((e^2)+1)),z[11]==z[9]+(({(f^2)-1,2f})/((f^2)+1))}])

Clear[e];
z[17]={0,0};
z[3]={1,0};
z[8]=z[17]+(({(a^2)-1,2a})/((a^2)+1));
z[10]=z[17]+(({(b^2)-1,2b})/((b^2)+1));
z[9]=z[3]+(({(c^2)-1,2c})/((c^2)+1));
z[14]=z[8]+(({(d^2)-1,2d})/((d^2)+1));
z[16]=z[3]+(({(e^2)-1,2e})/((e^2)+1));
z[11]=z[9]+(({(f^2)-1,2f})/((f^2)+1));
z[1]=z[8]+z[12]-z[17];
z[2]=-2z[3]+z[4]+z[5]-2z[8]-z[10]+z[12];
z[7]=z[3]-z[8]+z[10];
z[9]=z[3]-z[4]+z[10];
z[11]=2z[3]-z[4]+z[5]-2z[8]+2z[10]-z[12];
z[13]=-z[3]+2z[8]-z[10]+z[12];
z[14]=z[3]+z[6]+z[10]-z[8]-z[12];
z[15]=z[3]+z[10]-z[17];
z[16]=-2z[3]+2z[4]+2z[8]-2z[10]+z[12];

Array[z,17]//Column

Equations in a, b, c, d, e, f

Clear[a,b,c,d,e,f]
(eqn={
(a^2) b e-2 a (b^2) e-2 a b (e^2)+3 (b^2) (e^2)+(a^2)-2 a b-2 a e+(b^2)+b e+(e^2)==0,

(b^2) (d^2) (f^2)+2 (b^2) d f+b (d^2) f+2 b d (f^2)+(b^2)+2 b d+b f+2 d f+(f^2)+3==0,

(a^2) (b^2) (c^2)-3 (a^2) (b^2)+8 (a^2) b c-3 (a^2) (c^2)-8 a (b^2) c+8 a b (c^2)-3 (b^2) (c^2)+(a^2)+8 a b-8 a c-15 (b^2)+8 b c+(c^2)-3==0,

3 (a^2) (c^2) (d^2)+3 (a^2) (c^2)+16 (a^2) c d-(a^2) (d^2)+32 a (c^2) d+16 a c (d^2)+3 (c^2) (d^2)+15 (a^2)+16 a c+32 a d+35 (c^2)+16 c d+15 (d^2)+63==0,

(a^2) (d^2) (f^2)-(a^2) (d^2) e f+(a^2) d (e^2) f-(a^2) d e (f^2)+a (d^2) (e^2) f-a (d^2) e (f^2)+a d (e^2) (f^2)-(a^2) d e+(a^2) d f+(a^2) (e^2)-(a^2) e f-a (d^2) e+a (d^2) f+a d (e^2)+a d (f^2)+a (e^2) f-a e (f^2)+(d^2) (e^2)-(d^2) e f+d (e^2) f-d e (f^2)+(e^2) (f^2)+a d-a e+a f-d e+d f+3 (e^2)-e f+1==0,

a b c d (a b-a c-a d+2 b c+2 b d-2 c d)+(a^2) (c^2) (d^2)+(b^2) (c^2) (d^2)+(a^2) (b^2)-(a^2) b c-(a^2) b d+(a^2) c d+2 a (b^2) c+2 a (b^2) d-2 a b (c^2)-2 a b (d^2)+2 a (c^2) d+2 a c (d^2)+3 (b^2) (c^2)+(b^2) c d+3 (b^2) (d^2)-b (c^2) d-b c (d^2)-2 a b+2 a c+2 a d+6 (b^2)-b c-b d+(c^2)+c d+(d^2)+3==0
})//Column//TraditionalForm

Variables/@eqn[[All,1]]

var=Variables[Subtract@@@eqn]

Length/@{eqn,var}

onesoln=FindRoot[eqn,{a,2.43},{b,14.1},{c,5.16},{d,-2.72},{e,1.48},{f,.17},WorkingPrecision->50]

eqns/.onesoln

Resultant

Resultant[eqns[[3,1]],eqns[[4,1]],a]

Numeric solution

Length[nsoln=NSolve[eqns,var,Reals]]//Timing

eqns[[All,1]]/.nsoln

Chop[%]

nsoln//Column

Length[nsoln=NSolve[eqns,var,Reals,WorkingPrecision->20]]//Timing

nsoln

Homotopy method (adams)

polys=Subtract@@@eqn;

vars={a,b,c,d,e,f};

The  homotopy  method is not default here, because we don’t have high-precision homotopies -- roots found with machine precision are refined using FindRoot.

Length[nsoln=NSolve[eqn,vars,Reals,Method->"Homotopy",WorkingPrecision->50]]//Timing

Max[Abs[eqn[[All,1]]/. nsoln]]

sols=vars/.nsoln;

The number of roots found seems to be machine dependent. With mathkernel on byblis67 I get 56 roots, 54 distinct. Here (my local computer) only 52 distinct roots.

Length[Union[sols,SameTest->(Norm[#1-#2]<10^-50&)]]

Length[Union[sols,SameTest->(Norm[#1-#2]<1/10&)]]

usols=Union[sols,SameTest->(Norm[#1-#2]<1/10&)];

This  proves (using interval arithmetic) that the numeric solutions approximate actual solutions, hence there are at least 54 real solutions (according to the byblis67 result).

(rts=Reduce`FindSystemRoot[polys,vars,#,True,45]&/@usols)//Timing

Length[rts]

Element[vars/.rts,Reals]

Precision[rts]

Position[DistanceMatrix[N[vars/.rts,100]],_?(#<1/10&)]

Union[Subtract@@@%]

Homotopy method (eww)

polys=Subtract@@@eqn;

vars={a,b,c,d,e,f};

The  homotopy  method is not default here, because we don’t have high-precision homotopies -- roots found with machine precision are refined using FindRoot.

Length[nsoln=NSolve[eqn,vars,Reals,Method->"Homotopy",WorkingPrecision->50]]//Timing

Max[Abs[Subtract@@@eqn/. nsoln]]

sols=vars/.nsoln;

The number of roots found seems to be machine dependent. With mathkernel on byblis67 I get 56 roots, 54 distinct.  Adam's local computer finds only 52 distinct roots.  ewwmaclap finds:

Length[Union[sols,SameTest->(Norm[#1-#2]<10^-50&)]]

Length[usols=Union[sols,SameTest->(Norm[#1-#2]<1/10&)]]

This  proves (using interval arithmetic) that the numeric solutions approximate actual solutions, hence there are at least 54 real solutions (according to the byblis67 result).

(rts=Reduce`FindSystemRoot[polys,vars,#,True,45]&/@usols)//Timing

Length[rts]

Element[vars/.rts,Reals]

Precision[rts]

Position[DistanceMatrix[N[vars/.rts,100]],_?(#<1/10&)]

Union[Subtract@@@%]

Position[DistanceMatrix[N[vars/.rts,100]],_?(#<1.*^-10&)]

Union[Subtract@@@%]

Max[Abs[N[Subtract@@@eqn/.rts,10^4]]]//Timing

Max[Abs[N[eqn[[All,1]]/.rts,10^5]]]//Timing

MinimalPolynomial[(NumericalApproximation[Root, (RowDefault["-5.77", FEExpressionsNumericalApproximationElider]), Root[{{((#1)^2)-2 #1 #2+((#2)^2)-2 #1 #5+#2 #5+((#1)^2) #2 #5-2 #1 ((#2)^2) #5+((#5)^2)-2 #1 #2 ((#5)^2)+3 ((#2)^2) ((#5)^2)&,3+((#2)^2)+2 #2 #4+#2 #6+2 #4 #6+2 ((#2)^2) #4 #6+#2 ((#4)^2) #6+((#6)^2)+2 #2 #4 ((#6)^2)+((#2)^2) ((#4)^2) ((#6)^2)&,-3+((#1)^2)+8 #1 #2-15 ((#2)^2)-3 ((#1)^2) ((#2)^2)-8 #1 #3+8 #2 #3+8 «1»«1»«2» #3-8 #1 ((#2)^2) #3+((#3)^2)-3 ((#1)^2) ((#3)^2)+8 #1 #2 ((#3)^2)-3 ((#2)^2) ((#3)^2)+((#1)^2) ((#2)^2) ((#3)^2)&,«1»,1+#1 #4-#1 #5-#4 #5-((#1)^2) #4 #5-#1 ((#4)^2) #5+3 ((#5)^2)+((#1)^2) ((#5)^2)+#1 #4 ((#5)^2)+((#4)^2) ((#5)^2)+#1 #6+#4 #6+((#1)^2) #4 #6+#1 ((#4)^2) #6-#5 #6-((#1)^2) #5 #6-((#4)^2) #5 #6-((#1)^2) ((#4)^2) #5 #6+#1 ((#5)^2) #6+#4 ((#5)^2) #6+((#1)^2) #4 ((#5)^2) #6+#1 ((#4)^2) ((#5)^2) #6+#1 #4 ((#6)^2)+((#1)^2) ((#4)^2) ((#6)^2)-#1 #5 ((#6)^2)-#4 #5 ((#6)^2)-((#1)^2) #4 #5 ((#6)^2)-#1 ((#4)^2) #5 ((#6)^2)+((#5)^2) ((#6)^2)+#1 #4 ((#5)^2) ((#6)^2)&,3-2 #1 #2+6 ((#2)^2)+((#1)^2) ((#2)^2)+2 #1 #3-#2 #3-((#1)^2) #2 #3+2 #1 ((#2)^2) #3+((#3)^2)-2 #1 #2 ((#3)^2)+3 ((#2)^2) ((#3)^2)+2 #1 #4-#2 #4-((#1)^2) #2 #4+2 #1 ((#2)^2) #4+#3 #4+((#1)^2) #3 #4+((#2)^2) #3 #4+2 #1 ((#3)^2) #4-#2 ((#3)^2) #4+((#4)^2)-2 #1 #2 ((#4)^2)+3 ((#2)^2) ((#4)^2)+2 #1 #3 ((#4)^2)-#2 #3 ((#4)^2)+((#1)^2) ((#3)^2) ((#4)^2)+((#2)^2) ((#3)^2) ((#4)^2)+#1 #2 #3 #4 (#1 #2-#1 #3+2 #2 #3-#1 #4+2 #2 #4-2 #3 #4)&},«1»},1], ]),x]//Timing

Symbolic solution

This system has 48 real solutions (a,b,c,d,e, f) which translates into 12 different embeddings discounting symmetries. The particular solution given below generates the embedding in figure 8

Length[soln=Solve[eqns,{a,b,c,d,e,f},Reals]]//Timing

(Uses 140+ GB)

UnitDistance construction (Exoo 2016)

http://geombina.uccs.edu/?p=1590

It comes from the essay “Small Order Triangle-Free 4 Chromatic Unit Distance Graphs” that appear in the October issue (2) of Volume XXVI of Geocombinatorics

MR3561165
Exoo, Geoffrey(1-INS); Ismailescu, Dan(1-HOFS)
Small order triangle-free 4-chromatic unit distance graphs. 
Geombinatorics 26 (2016), no. 2, 49–64.

In the paper under review, triangle-free 4-chromatic unit distance graphs with 21, 19 and 17 vertices are constructed. Evidence that the value 17 might actually be the smallest order of such a graph is presented.

From Ed Pegg, Jr.
"Fun with Algebraic Quadratic Spaces" comp pros NB
March 8, 2018

"For example, the Exoo-Ismailescu graph is a record-setting triangle-free unit-distance 4-chromatic graph with exact coordinates requiring order-128 polynomials. Incredibly, the vertices can instead be based on the seven color vectors shown, allowing a simpler solution based on GroebnerBasis[].  But that method is too complicated for an opening paragraph. "

gr=With[{vveecc=Normal[]},With[{vv=vveecc[[1]], ee=vveecc[[2]],cc=vveecc[[3]]},
Graphics[{Thick,Table[{cc[[n]],Table[Line[vv[[ee[[n,k]]]]],{k,1,Length[ee[[n]]]}] },{n,1,8}], EdgeForm[Black],White,Table[{Disk[vv[[n]],.05],Black,Text[n,vv[[n]]]}, {n,1,Length[vv]}]}, ImageSize-> Large]]]

ec=Cases[gr,Line[x_]:>x,∞];

Length[v=Flatten[ec,1]//Union]

e=ec/.Thread[v->Range[Length[v]]];

g=System`Graph[Range[17],UndirectedEdge@@@e,VertexCoordinates->v]

UnitDistanceGraphQ[g]

TriangleFreeGraphQ[g]

Girth[CombinatoricaGraph@g]

ChromaticNumber[g]

Exact construction attempt from above

xform=Sort[{13->5,17->13,14->9,9->17,4->11,11->8,5->3,7->10,10->12,2->7,1->4,6->14,3->15,8->16,12->1,16->6,15->2}]

Complement[Range[17],xform[[All,1]]]

Complement[Range[17],xform[[All,2]]]

e=Sort[Sort/@(GraphData[gn="ExooIsmailescuGraph","Edges","List"]/.xform)]

ee={{1,8},{1,12},{1,15},{2,9},{2,10},{2,16},{3,9},{3,15},{3,16},{3,17},{4,10},{4,11},{4,16},{5,11},{5,13},{5,16},{6,12},{6,13},{6,14},{7,12},{7,14},{7,15},{8,13},{8,14},{8,17},{9,11},{9,13},{10,15},{10,17},{11,14},{12,17}};

eqn=Join[((x[#1]-x[#2])^2+(y[#1]-y[#2])^2==1)&@@@ee,
{(* Red *)
x[13]==0,y[13]==0,
x[8]==-1,y[8]==0,
x[14]==x[6]-1,y[14]==y[6],
x[7]==x[12]-1,y[7]==y[12]
},
{(* Magenta *)
x[8]==x[14]+x[13]-x[6],
y[8]==y[14]+y[13]-y[6]
},
{(* Brown *)
x[17]==x[10]+x[3]-x[15],
y[17]==y[10]+y[3]-y[15]
},
{(* Yellow *)
x[9]==x[11]+x[13]-x[5],
y[9]==y[11]+y[13]-y[5]
},
{(* Green *)
x[17]==x[8]+x[7]-x[15]==x[8]+x[12]-x[1],
y[17]==y[8]+y[7]-y[15]==y[8]+y[12]-y[1]
},
{(* Blue *)
x[11]==x[5]+x[9]-x[13]==x[5]+x[10]-x[2]==x[5]+x[4]-x[16],
y[11]==y[5]+y[9]-y[13]==y[5]+y[10]-y[2]==y[5]+y[4]-y[16]
}];

newv=GraphData["ExooIsmailescuGraph17","VertexCoordinates"][[InversePermutation@xform[[All,2]]]]

eqn/.Flatten[Thread/@Thread[Table[{x[i],y[i]},{i,17}]->newv]]

And@@%

Length[eqn]

vars=Flatten[Table[{{x[i],newv[[i,1]]},{y[i],newv[[i,2]]}},{i,17}],1];

Eliminate[{(* Blue *)
x[11]==x[5]+x[9]-x[13]==x[5]+x[10]-x[2]==x[5]+x[4]-x[16],
y[11]==y[5]+y[9]-y[13]==y[5]+y[10]-y[2]==y[5]+y[4]-y[16]
},{x[9],y[9]}]

Eliminate[{(* Green *)
x[17]==x[8]+x[7]-x[15]==x[8]+x[12]-x[1],
y[17]==y[8]+y[7]-y[15]==y[8]+y[12]-y[1]
},{x[17],y[17],x[7],y[7]}]

red={
x[13]->0,y[13]->0,
x[8]->-1,y[8]->0,
x[14]->x[6]-1,y[14]->y[6],
x[7]->x[12]-1,y[7]->y[12]
};
magenta={
x[8]->x[14]+x[13]-x[6],
y[8]->y[14]+y[13]-y[6]
};
brown={
x[17]->x[10]+x[3]-x[15],
y[17]->y[10]+y[3]-y[15]
};
yellow={
x[9]->x[11]+x[13]-x[5],
y[9]->y[11]+y[13]-y[5]
};
blue={
x[2]->-x[4]+x[10]+x[16],
x[4]->-x[5]+x[11]+x[16],
y[2]->-y[4]+y[10]+y[16],
y[4]->-y[5]+y[11]+y[16]
};

simpeqn=Union[Simplify@DeleteCases[((x[#1]-x[#2])^2+(y[#1]-y[#2])^2-1)&@@@ee/.yellow/.magenta/.brown/.blue/.red,0]]

Length[simpeqn={2 x[1]+((x[1])^2)+((y[1])^2),-1+((x[5])^2)+((y[5])^2),-1+((x[6])^2)+((y[6])^2),-1+(((x[4]-x[10]))^2)+(((y[4]-y[10]))^2),-1+(((x[5]-x[11]))^2)+(((y[5]-y[11]))^2),-1+(((x[3]+x[5]-x[11]))^2)+(((y[3]+y[5]-y[11]))^2),-1+(((1-x[6]+x[11]))^2)+(((y[6]-y[11]))^2),-1+(((x[1]-x[12]))^2)+(((y[1]-y[12]))^2),-1+(((x[6]-x[12]))^2)+(((y[6]-y[12]))^2),-1+(((x[1]-x[15]))^2)+(((y[1]-y[15]))^2),-1+(((x[3]-x[15]))^2)+(((y[3]-y[15]))^2),-1+(((x[10]-x[15]))^2)+(((y[10]-y[15]))^2),-1+(((1+x[3]+x[10]-x[15]))^2)+(((y[3]+y[10]-y[15]))^2),-1+(((x[3]+x[10]-x[12]-x[15]))^2)+(((y[3]+y[10]-y[12]-y[15]))^2),-1+(((1-x[12]+x[15]))^2)+(((y[12]-y[15]))^2),-1+(((x[3]-x[16]))^2)+(((y[3]-y[16]))^2),-1+(((x[4]-x[16]))^2)+(((y[4]-y[16]))^2),-1+(((x[5]-x[16]))^2)+(((y[5]-y[16]))^2),-1+(((x[5]+x[10]-x[11]-x[16]))^2)+(((y[5]+y[10]-y[11]-y[16]))^2),-1+(((-x[4]+x[5]+x[10]-x[11]+x[16]))^2)+(((-y[4]+y[5]+y[10]-y[11]+y[16]))^2)}]

simpeqn//Column//TraditionalForm

Table[{x[i],y[i]},{i,17}]->newv

simpeqn/.Flatten[Thread/@Thread[Table[{x[i],y[i]},{i,17}]->newv]]//Chop

vars=Variables[simpeqn]

Length/@{simpeqn,vars}

varandinit=Table[{var,newv[[var[[1]],Head[var]/.{x->1,y->2}]]},{var,vars}];

(soln=FindRoot[simpeqn,varandinit,WorkingPrecision->100000])//N//Timing

coords=Transpose[{Array[x,17],Array[y,17]}]/.yellow/.magenta/.brown/.blue/.red

Length[coords]

g=Graph[Range[Length[coords]],ee,VertexCoordinates->(coords/.soln)]

GraphEmbedding[g][[1,1]]//Precision

RecognizeGraph[g]

UnitDistanceGraphEmbeddingQ[g]

"ExooIsmailescuGraph19"

Embeddings from
Exoo, G. and Ismailescu, D.  "Small order triangle-free 4-chromatic unit distance graphs."  Geombinatorics 26, no. 2, 49–64, 2016.

GraphData

ExooIsmailescuGraph19Core

(g=GraphData[gn="ExooIsmailescuGraph19Core"])//StyleGraphs

UnitDistanceGraphEmbeddingQ[g]

GraphEmbedding[g]

LamanGraphQ[g]

GraphData[gn,"Laman"]

TriangleFreeGraphQ[g]

ChromaticNumber[g]

Laman subgraph

GraphData[gn,"Graph","Labeled"]

LamanGraphQ[VertexDelete[GraphData["ExooIsmailescuGraph19Core"],2]]

Do[Print[{VertexCount[g]-n,Select[Subsets[VertexList[g],{n}],LamanGraphQ[VertexDelete[g,#]]&]//Timing}],{n,13}]

ExooIsmailescuGraph19

(g=GraphData[gn="ExooIsmailescuGraph19"])//StyleGraphs

VertexCount[g]

UnitDistanceGraphQ[g]

UnitDistanceGraphQ[g,WorkingPrecision->∞]//RootReduce//Timing

TriangleFreeGraphQ[g]

ChromaticNumber[g]

GraphEmbedding[g]

ExooIsmailescuGraph19Core

v=With[{s=(Sqrt[7])/3,t=(Sqrt[2])/3,o=1/3},{
(*1*){0,0},
(*2*){2s,0},
(*3*){-o,0},
(*4*){s,-t},
(*5*){s,t},
(*6*){o+s,-t},
(*7*){s-o,t},
(*8*){s-o,-t},
(*9*){-2o+s,-t},
(*10*){-o/2,(Sqrt[35])/6},
(*11*){(-o+2s)/2,((Sqrt[35])-2(Sqrt[2]))/6},
(*12*){(o+2s)/2,((Sqrt[35])-2(Sqrt[2]))/6},
(*13*){(-o+2s)/2,((Sqrt[35])+2(Sqrt[2]))/6},
(*14*){(-3+2(Sqrt[7]))/6,((Sqrt[35])-2(Sqrt[2]))/6}
}];

Length[v]

e=Select[Subsets[Range[Length[v]],{2}],SquaredEuclideanDistance@@v[[#]]==1.&]

ExooIsmailescuGraph19Core=System`Graph[Range[Length[v]],UndirectedEdge@@@e,VertexCoordinates->v]

UnitDistanceGraphQ[ExooIsmailescuGraph19Core]

Equations

(eqns={
(55+24√7)a^2b^2+19(a^2+b^2)+72a b+55−24√7==0,
3a^2c^2+(√7−2)(a^2+c^2)+(7√7−17)a c+9√7−24==0,
a^2c^2−2a^2+9a c−5c^2+1==0
})//Column//TraditionalForm

Sort/@NSolve[eqns,{a,b,c},Reals]//Column

solns19=Sort/@Solve[eqns,{a,b,c},Reals]//RootReduce

solns19//N//Column

z1={0,0};
z2={2(Sqrt[7])/3,0};
z3={-1/3,0};
z15=z1+{((1-(a^2))/(1+(a^2))),((2a)/(1+(a^2)))};
z17=z1+{((1-(b^2))/(1+(b^2))),((2b)/(1+(b^2)))};
z19=z3+{((1-(c^2))/(1+(c^2))),((2c)/(1+(c^2)))};
z16=z15+z17-z1;
z18=z2+z17-z16;

(znew=Symbol["z"<>ToString[#]]&/@Range[15,19]/.solns19[[-1]]//N)//Column

Symbol["z"<>ToString[#]]&/@Range[15,19]/.solns19[[-1]]

v19exact=Symbol["z"<>ToString[#]]&/@Range[15,19]/.solns19[[-1]]//RootReduce;//Timing

v19exact

Length[v19exact]

N[v19exact]

ExooIsmailescuGraph19

v19=Join[v,v19exact]

e19=Select[Subsets[Range[Length[v19]],{2}],Abs[EuclideanDistance@@v19[[#]]-1]<1*^-3&]

ExooIsmailescuGraph19=System`Graph[Range[Length[v19]],UndirectedEdge@@@e19,VertexCoordinates->v19,VertexLabels->"Name"]

UnitDistanceGraphQ[ExooIsmailescuGraph19]

GraphData

file=OpenWrite["~/e-i.m"]

WriteString[file,GraphDataString[ExooIsmailescuGraph19Core,
"StandardName"->"ExooIsmailescuGraph19Core",
"Name"->"Exoo\[Hyphen]Ismailescu graph 19 core",
Debug->True
]]

WriteString[file,GraphDataString[ExooIsmailescuGraph19,
"StandardName"->"ExooIsmailescuGraph19",
"Name"->"Exoo\[Hyphen]Ismailescu graph 19",
"Skip"->{"AdjacencyMatrices","SpanningTrees"},
Debug->True
]]

Close[file]

Embeddings

Names

GraphData["ExooIsmailescuGraph19","StandardName"]

GraphData["ExooIsmailescuGraph19","StandardNames"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ExooIsmailescuGraph19","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData["ExooIsmailescuGraph19","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

Select[%,Max[OuterFace[#]]<=GraphData["ExooIsmailescuGraph19","V"]&]

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

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

LabelGraph@

GraphPlot@PlanarGraphEmebdding[,2,"OuterFace"->{6,12,13,14,9}]

g=GraphPlot@EdgeAdd[VertexDelete[GraphicsToGraph@,Range[20,26]],UndirectedEdge@@@{{3,7},{11,8},{8,14},{7,13},{5,8},{10,13},{4,12},{5,6},{2,5},{4,1},{18,17},{16,2},{10,11},{3,19}}]

g=GraphicsToGraph@

RecognizeGraph@g

RectilinearCrossingCount[g]

Circulant

GraphData["ExooIsmailescuGraph19","Circulant"]

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

Halin

GraphData["ExooIsmailescuGraph19","Halin"]

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

Rigid

GraphData["ExooIsmailescuGraph19","Rigid"]

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

Flexible

GraphData["ExooIsmailescuGraph19","Flexible"]

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

LCF

GraphData["ExooIsmailescuGraph19","LCF"]

GraphData["ExooIsmailescuGraph19","HamiltonianCycleCount"]

GraphData["ExooIsmailescuGraph19","LCFSignature"]

GraphData["ExooIsmailescuGraph19","LCFNotations"]

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

UnitDistance

GraphData["ExooIsmailescuGraph19","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["ExooIsmailescuGraph19","VertexList"],GraphData["ExooIsmailescuGraph19","EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["ExooIsmailescuGraph19","Matchstick"]

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

3D default

Graph3D[GraphData["ExooIsmailescuGraph19","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ExooIsmailescuGraph19","Polyhedral"]

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

"ExooIsmailescuGraph21"

Embeddings from
Exoo, G. and Ismailescu, D.  "Small order triangle-free 4-chromatic unit distance graphs."  Geombinatorics 26, no. 2, 49–64, 2016.

GraphData

ExooIsmailescuGraph21Core

g=GraphData[gn="ExooIsmailescuGraph21Core"]

UnitDistanceGraphQ[g,WorkingPrecision->∞]

GraphEmbedding[g]

ExooIsmailescuGraph21

g=GraphData[gn="ExooIsmailescuGraph21"]

GraphEmbedding[g]

UnitDistanceGraphQ[g]

UnitDistanceGraphQ[g,WorkingPrecision->1000]

UnitDistanceGraphQ[g,WorkingPrecision->Infinity]//RootReduce//Timing

TriangleFreeGraphQ[g]

ChromaticNumber[g]

ExooIsmailescuGraph21Core

v21core=With[{s=(Sqrt[7])/4,f=1/4},{
{-f+s,f+s},
{-f-s,f-s},
{f+s,3f+s},
{f-s,f+s},
{f+s,f-s},
{-f-s,3f+s},
{0,1},
{-2f,2f},
{2f,2f},
{0,2(f+s)},
{0,0}
}];

e=Select[Subsets[Range[Length[v]],{2}],SquaredEuclideanDistance@@v[[#]]==1.&]

ExooIsmailescuGraph21Core=System`Graph[Range[Length[v]],UndirectedEdge@@@e,VertexCoordinates->v,VertexLabels->"Name"]

UnitDistanceGraphQ[ExooIsmailescuGraph21Core,WorkingPrecision->∞]

ChromaticNumber[ExooIsmailescuGraph21Core]

Equations

(eqns={
(13−4√7)a^2b^2+4√7(a+b)(a b+1)+5(a^2+b^2)+16a b+13+4√7==0,
 (5−√7)a^2c^2+(2√7+2)(a+c)(1+a c)+(3+√7)(a^2+c^2)+8a c+9+3√7==0,
a^2c^2−4a^2c+4a c^2−11a^2+16a c−3c^2+4a−4c+1==0})//Column//TraditionalForm

Factor[Resultant[Sequence@@(Rest[eqns]/.e_Equal:>Subtract@@e),c]][[-1]]

Roots[-51-19 (Sqrt[7])+105 a+33 (Sqrt[7]) a-6 (a^2)+42 (Sqrt[7]) (a^2)-70 (a^3)-166 (Sqrt[7]) (a^3)-531 (a^4)+45 (Sqrt[7]) (a^4)+273 (a^5)-135 (Sqrt[7]) (a^5)-128 (a^6)+48 (Sqrt[7]) (a^6)==0,a]

N[%]

Factor[Resultant[Sequence@@(Rest[eqns]/.e_Equal:>Subtract@@e),a]][[-1]]

Sort/@NSolve[eqns,{a,b,c},Reals]//Column

(solns21=Sort/@Solve[eqns,{a,b,c},Reals]//RootReduce)//Column

N[solns21]//Column

z1={(-1+√7)/4,(1+√7)/4};
z2={(-1-√7)/4,(1-√7)/4};
z3={(1+√7)/4,(3+√7)/4};
z12=z1+{(1-(a^2))/(1+(a^2)),(2a)/(1+(a^2))};
z14=z1+{(1-(b^2))/(1+(b^2)),(2b)/(1+(b^2))};
z16=z3+{(1-(c^2))/(1+(c^2)),(2c)/(1+(c^2))};
z13=z12+z14-z1;
z15=z2+z14-z13;
z17={-1,1}z12;
z18={-1,1}z13;
z19={-1,1}z14;
z20={-1,1}z15;
z21={-1,1}z16;

(znew=Symbol["z"<>ToString[#]]&/@Range[12,21]/.solns21[[6]]//N)//Column

z12rr=z12/.solns21[[6]]//RootReduce

z14rr=z14/.solns21[[6]]//RootReduce

z14rr={Root[155235917992-20267085796860 #1+230885031686253 ((#1)^2)+16194307710426608 ((#1)^3)-59845806402954684 ((#1)^4)-4544573109642780984 ((#1)^5)-42671719435510402300 ((#1)^6)-184031487436799500848 ((#1)^7)-407535045826912918992 ((#1)^8)-317604524253939277824 ((#1)^9)+665278617231667551168 ((#1)^10)+2263316493145912549632 ((#1)^11)+2929480090075786689792 ((#1)^12)+1432738565564345561088 ((#1)^13)-1563757863212416499712 ((#1)^14)-4316605423594601840640 ((#1)^15)-5479823726949537939456 ((#1)^16)-4256268479772386918400 ((#1)^17)-883805656736971358208 ((#1)^18)+2581917957411053764608 ((#1)^19)+3840865091166608031744 ((#1)^20)+2806011522002429411328 ((#1)^21)+1208590451222262054912 ((#1)^22)+292525077365897822208 ((#1)^23)+30792113406936612864 ((#1)^24)&,6],Root[-5619023983+2096431834602 #1+28406078495529 ((#1)^2)-4177635954016056 ((#1)^3)+10121723588692968 ((#1)^4)+789891109489509888 ((#1)^5)-5934370672451838988 ((#1)^6)+14426492756960782512 ((#1)^7)-5677529253387367824 ((#1)^8)-28745274685479881088 ((#1)^9)+60627500752970305728 ((#1)^10)-91435224377014043904 ((#1)^11)+40408989408850003200 ((#1)^12)+193305137995525828608 ((#1)^13)-259264278264366563328 ((#1)^14)+14522176516240834560 ((#1)^15)+62130879875105685504 ((#1)^16)-80079641650070028288 ((#1)^17)+240575706512329015296 ((#1)^18)-170067037487408087040 ((#1)^19)-134084017267119489024 ((#1)^20)+223323009995621007360 ((#1)^21)-30792113406936612864 ((#1)^22)-76980283517341532160 ((#1)^23)+30792113406936612864 ((#1)^24)&,15]};

z16rr=z16/.solns21[[6]]//RootReduce

z13rr=z12rr+z14rr-z1//RootReduce//Timing

z13rr={Root[-5619023983-2096431834602 #1+28406078495529 ((#1)^2)+4177635954016056 ((#1)^3)+10121723588692968 ((#1)^4)-789891109489509888 ((#1)^5)-5934370672451838988 ((#1)^6)-14426492756960782512 ((#1)^7)-5677529253387367824 ((#1)^8)+28745274685479881088 ((#1)^9)+60627500752970305728 ((#1)^10)+91435224377014043904 ((#1)^11)+40408989408850003200 ((#1)^12)-193305137995525828608 ((#1)^13)-259264278264366563328 ((#1)^14)-14522176516240834560 ((#1)^15)+62130879875105685504 ((#1)^16)+80079641650070028288 ((#1)^17)+240575706512329015296 ((#1)^18)+170067037487408087040 ((#1)^19)-134084017267119489024 ((#1)^20)-223323009995621007360 ((#1)^21)-30792113406936612864 ((#1)^22)+76980283517341532160 ((#1)^23)+30792113406936612864 ((#1)^24)&,3],Root[155235917992+20267085796860 #1+230885031686253 ((#1)^2)-16194307710426608 ((#1)^3)-59845806402954684 ((#1)^4)+4544573109642780984 ((#1)^5)-42671719435510402300 ((#1)^6)+184031487436799500848 ((#1)^7)-407535045826912918992 ((#1)^8)+317604524253939277824 ((#1)^9)+665278617231667551168 ((#1)^10)-2263316493145912549632 ((#1)^11)+2929480090075786689792 ((#1)^12)-1432738565564345561088 ((#1)^13)-1563757863212416499712 ((#1)^14)+4316605423594601840640 ((#1)^15)-5479823726949537939456 ((#1)^16)+4256268479772386918400 ((#1)^17)-883805656736971358208 ((#1)^18)-2581917957411053764608 ((#1)^19)+3840865091166608031744 ((#1)^20)-2806011522002429411328 ((#1)^21)+1208590451222262054912 ((#1)^22)-292525077365897822208 ((#1)^23)+30792113406936612864 ((#1)^24)&,13]};

z15rr=z1+z2-z12rr//RootReduce

zexact21=Join[
{z12rr,z13rr,z14rr,z15rr,z16rr},
{-1,1}#&/@{z12rr,z13rr,z14rr,z15rr,z16rr}
]

N[zexact21]

Flexible

GraphData["ExooIsmailescuGraph21","Laman"]

GraphData["ExooIsmailescuGraph21",{"V","E"}]

2 21-3

...so one extra edge

LamanGraphQ[GraphData["ExooIsmailescuGraph21"]]

https://math.stackexchange.com/questions/3958839/are-4-chromatic-3-connected-unit-distance-graphs-always-rigid

Import["https://i.stack.imgur.com/3C2Ew.gif",{"GIF","Animation"}]

ExooIsmailescuGraph21

GetGraphData["ExooIsmailescuGraph21","File"]

v21=Join[v21core,zexact21]

N[%]

e21=Select[Subsets[Range[Length[v21]],{2}],Abs[EuclideanDistance@@v21[[#]]-1]<1*^-3&]

ExooIsmailescuGraph21=System`Graph[Range[Length[v21]],UndirectedEdge@@@e21,VertexCoordinates->v21,VertexLabels->"Name"]

RecognizeGraph[ExooIsmailescuGraph21]

UnitDistanceGraphQ[ExooIsmailescuGraph21]

UnitDistanceGraphQ[ExooIsmailescuGraph21,WorkingPrecision->100]

UnitDistanceGraphQ[ExooIsmailescuGraph21,WorkingPrecision->Infinity]//RootReduce//Timing

GraphData

file=OpenAppend["~/e-i.m"]

WriteString[file,GraphDataString[ExooIsmailescuGraph21Core,
"StandardName"->"ExooIsmailescuGraph21Core",
"Name"->"Exoo\[Hyphen]Ismailescu graph 21 core",
"Skip"->{"AdjacencyMatrices","SpanningTrees"},
Debug->True
]]

WriteString[file,GraphDataString[ExooIsmailescuGraph21,
"StandardName"->"ExooIsmailescuGraph21",
"Name"->"Exoo\[Hyphen]Ismailescu graph 21",
"Skip"->{"AdjacencyMatrices","SpanningTrees"},
Debug->True
]]

Close[file]

"ExooIsmailescuGraph21" (21 nodes)

Embeddings

GraphData["ExooIsmailescuGraph21","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ExooIsmailescuGraph21","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Planar

GraphData["ExooIsmailescuGraph21","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

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

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

faces=ReverseSort@SymmetricallyDistinctFaces[g]

Tally[ReverseSort[Length/@faces]]

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

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

Table[MinimalCrossingGraph[GraphData["ExooIsmailescuGraph21"],"CrossingNumber"->cn,RandomSeed->i],{i,500}]//Union//Timing

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ExooIsmailescuGraph21","Circulant"]

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

Halin

GraphData["ExooIsmailescuGraph21","Halin"]

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

Rigid

GraphData["ExooIsmailescuGraph21","Rigid"]

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

Flexible

GraphData["ExooIsmailescuGraph21","Flexible"]

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

LCF

GraphData["ExooIsmailescuGraph21","LCF"]

GraphData["ExooIsmailescuGraph21","HamiltonianCycleCount"]

GraphData["ExooIsmailescuGraph21","LCFSignature"]

GraphData["ExooIsmailescuGraph21","LCFNotations"]

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

UnitDistance

GraphData["ExooIsmailescuGraph21","UnitDistance"]

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

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

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

UnitDistance by refinement

UnitDistanceEmbeddingRefine[Graph[GraphData["ExooIsmailescuGraph21","VertexList"],GraphData["ExooIsmailescuGraph21","EdgeList"]]]

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["ExooIsmailescuGraph21","Matchstick"]

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

3D default

Graph3D[GraphData["ExooIsmailescuGraph21","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ExooIsmailescuGraph21","Polyhedral"]

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

"ExooIsmailescuGraph40"

Embeddings

GraphData["ExooIsmailescuGraph40","Graph","All"]

GraphData["ExooIsmailescuGraph40","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph40","CrossingNumber"]

GraphData["ExooIsmailescuGraph40","LCF"]

GraphData["ExooIsmailescuGraph40","Hamiltonian"]

GraphData["ExooIsmailescuGraph40","UnitDistance"]

GraphData["ExooIsmailescuGraph40","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1805.00157.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

notation[{a_,b_,c_,d_}]:={a(Sqrt[3])+b(Sqrt[11]),c+d(Sqrt[33])}/36

G40Vertices=notation[ToExpression["{"<>#<>"}"]]&/@StringReplace[StringCases[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/ExooIsmailescu/G40_vertices.txt","String"],ShortestMatch["["..~~s__~~"]"]:>s],"["|"]"->""]

G40=With[{v=G40Vertices},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

GraphDataString

file=OpenAppend["~/exoo.m"]

WriteString[file,GraphDataString[G40,
"StandardName"->"ExooIsmailescuGraph40",
"Name"->"Exoo\[Hyphen]Ismailescu graph 40",
TimeConstraint->5
]]

Close[file]

"ExooIsmailescuGraph49"

Embeddings

GraphData["ExooIsmailescuGraph49","Graph","All"]

GraphData["ExooIsmailescuGraph49","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph49","CN"]

GraphData["ExooIsmailescuGraph49","LCF"]

GraphData["ExooIsmailescuGraph49","Hamiltonian"]

GraphData["ExooIsmailescuGraph49","UnitDistance"]

UnitDistanceGraphEmbeddingQ[GraphData["ExooIsmailescuGraph49"]]

GraphData["ExooIsmailescuGraph49","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1805.00157.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

notation[{a_,b_,c_,d_}]:={a(Sqrt[3])+b(Sqrt[11]),c+d(Sqrt[33])}/36

G49Vertices=notation[ToExpression["{"<>#<>"}"]]&/@StringReplace[StringCases[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/ExooIsmailescu/G49_vertices.txt","String"],ShortestMatch["["..~~s__~~"]"]:>s],"["|"]"->""]

G49=With[{v=G49Vertices},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

GraphDataString

file=OpenAppend["~/exoo.m"]

WriteString[file,GraphDataString[G49,
"StandardName"->"ExooIsmailescuGraph49",
"Name"->"Exoo\[Hyphen]Ismailescu graph 49",
TimeConstraint->5
]]

Close[file]

"ExooIsmailescuGraph51"

Embeddings

GraphData["ExooIsmailescuGraph51","Graph","All"]

GraphData["ExooIsmailescuGraph51","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph51","CN"]

GraphData["ExooIsmailescuGraph51","LCF"]

GraphData["ExooIsmailescuGraph51","Hamiltonian"]

GraphData["ExooIsmailescuGraph51","UnitDistance"]

GraphData["ExooIsmailescuGraph51","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1805.00157.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

G51=With[{v=Take[G627Vertices,51]},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

GraphAutomorphismGroup[G51]//GroupOrder

HighlightGraph[G51,{1,2,3}]

VertexChromaticNumber[G51]

(poly=ChromaticPolynomial[G51,x])//Timing

GraphDataString

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

WriteString[file,GraphDataString[G51,
"StandardName"->"ExooIsmailescuGraph51",
"Name"->"Exoo\[Hyphen]Ismailescu graph 51",
TimeConstraint->5
]]

Close[file]

"ExooIsmailescuGraph79"

Embeddings

GraphData["ExooIsmailescuGraph79","Graph","All"]

GraphData["ExooIsmailescuGraph79","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph79","CN"]

GraphData["ExooIsmailescuGraph79","LCF"]

GraphData["ExooIsmailescuGraph79","Hamiltonian"]

GraphData["ExooIsmailescuGraph79","UnitDistance"]

GraphData["ExooIsmailescuGraph79","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1805.00157.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

G79Vertices=Join[G40Vertices,RotationMatrix[ArcCos[(119/128)]].#&/@G40Vertices]//FullSimplify//Union

Length[G79Vertices]

G79=With[{v=G79Vertices},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

EdgeCount[G79]

file=OpenAppend["~/exoo.m"]

<<MathWorld`Graphs`

WriteString[file,GraphDataString[G79,
"StandardName"->"ExooIsmailescuGraph79",
"Name"->"Exoo\[Hyphen]Ismailescu graph 79",
TimeConstraint->5
]]

"ExooIsmailescuGraph205" (G)

Embeddings

GraphData["ExooIsmailescuGraph205","Graph","All"]

GraphData["ExooIsmailescuGraph205","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph205","CN"]

GraphData["ExooIsmailescuGraph205","Hamiltonian"]

GraphData["ExooIsmailescuGraph205","LCF"]

GraphData["ExooIsmailescuGraph205","UnitDistance"]

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

GraphData["ExooIsmailescuGraph205","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1909.13177.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

G205Vertices=Drop[G214Vertices,-9]

Distance12Edges[v_,opts___?OptionQ]:=Module[{eps=Lookup[{opts},Tolerance,1*^-6,d]},UndirectedEdge@@@Select[Subsets[Range[Length[v]],{2}],Abs[(d=EuclideanDistance@@v[[#]])-1]<eps||Abs[d-2]<eps&]//Quiet]

G205=With[{v=G205Vertices},Graph[Range[Length[v]],Distance12Edges[v],VertexCoordinates->v]]

{VertexCount[G205],EdgeCount[G205]}

EdgeLengths[G205]//FullSimplify//Tally//Quiet

Claim 2.1. The graph G has 205 vertices, 966 edges of length 1, 423 edges of length 2, and exactly 18 5-colorings.

bug(415898): FindVertexColoring[g, PerformanceGoal -> "Quality"] and VertexChromaticNumber incorrectly return non-minimal colorings

VertexChromaticNumber[G205,PerformanceGoal->"Quality"]//Timing

(should be 5)

<<IGraphM`

IGChromaticNumber[G205]//Timing

GraphDataString

file=OpenAppend["~/exoo.m"]

WriteString[file,GraphDataString[G205,
"StandardName"->"ExooIsmailescuGraph205",
"Name"->"Exoo\[Hyphen]Ismailescu graph 205",
"Skip"->{"CliqueCoveringNumber","DominatingSet","TotalDominatingSet","VertexCover"},
TimeConstraint->5
]]

"ExooIsmailescuGraph214" (H)

Embeddings

GraphData["ExooIsmailescuGraph214","Graph","All"]

GraphData["ExooIsmailescuGraph214","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph214","CN"]

GraphData["ExooIsmailescuGraph214","Hamiltonian"]

GraphData["ExooIsmailescuGraph214","LCF"]

GraphData["ExooIsmailescuGraph214","UnitDistance"]

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

GraphData["ExooIsmailescuGraph214","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1909.13177.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

notation[{a_,b_,c_,d_}]:={a(Sqrt[3])+b(Sqrt[11]),c+d(Sqrt[33])}/12

G214Vertices=notation[ToExpression["{"<>#<>"}"]]&/@StringCases[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/ExooIsmailescu/vertices.1.2.txt","String"],ShortestMatch["["..~~s__~~"]"]:>s]

Distance12Edges[v_,opts___?OptionQ]:=Module[{eps=Lookup[{opts},Tolerance,1*^-6,d]},UndirectedEdge@@@Select[Subsets[Range[Length[v]],{2}],Abs[(d=EuclideanDistance@@v[[#]])-1]<eps||Abs[d-2]<eps&]//Quiet]

G214=With[{v=G214Vertices},Graph[Range[Length[v]],Distance12Edges[v],VertexCoordinates->v]]

EdgeCount[G214]

EdgeLengths[G214]//FullSimplify//Tally//Quiet

Claim 2.2. The graph H defined above has 214 vertices, 1004 edges of length 1, 446 edges of length 2, and exactly 35 5-colorings. Moreover, in each of these colorings, vertices A and B are of the same color.

bug(415898): FindVertexColoring[g, PerformanceGoal -> "Quality"] and VertexChromaticNumber incorrectly return non-minimal colorings

VertexChromaticNumber[G214,PerformanceGoal->"Quality"]//Timing

(should be 5)

<<IGraphM`

IGChromaticNumber[G214]//Timing

GraphDataString

file=OpenAppend["~/exoo.m"]

WriteString[file,GraphDataString[G214,
"StandardName"->"ExooIsmailescuGraph214",
"Name"->"Exoo\[Hyphen]Ismailescu graph 214",
"Skip"->{"CliqueCoveringNumber","DominatingSet","TotalDominatingSet","VertexCover"},
TimeConstraint->5
]]

"ExooIsmailescuGraph627"

Embeddings

GraphData["ExooIsmailescuGraph627","Graph","All"]

GraphData["ExooIsmailescuGraph627","Graph","MinimalCrossing"]

GraphData["ExooIsmailescuGraph627","CN"]

GraphData["ExooIsmailescuGraph627","Hamiltonian"]

GraphData["ExooIsmailescuGraph627","LCF"]

GraphData["ExooIsmailescuGraph627","UnitDistance"]

GraphData["ExooIsmailescuGraph627","Graph","UnitDistance"]

Construction

https://arxiv.org/pdf/1805.00157.pdf

http://cs.indstate.edu/ge/ExooIsmailescuData/

notation[{a_,b_,c_,d_}]:={a(Sqrt[3])+b(Sqrt[11]),c+d(Sqrt[33])}/36

G627Vertices=notation[ToExpression["{"<>#<>"}"]]&/@StringReplace[StringCases[Import["/Users/eww/Documents/Mathematica/Paclets/GraphData/Collections/UnitDistance/ExooIsmailescu/G627.txt","String"],ShortestMatch["["..~~s__~~"]"]:>s],"["|"]"->""]

Length[G627Vertices]

<<MathWorld`Graphs`

G627=With[{v=G627Vertices},Graph[Range[Length[v]],UnitEdges[v],VertexCoordinates->v]]

EdgeCount[G627]

UnitDistanceGraphEmbeddingQ[G627,WorkingPrecision->∞]//Timing//Quiet

VertexChromaticNumber[G627]//Timing

(Subscript[G, 627]) cannot be 4-colored when A, B and C are colored the same

HighlightGraph[G627,{1,2,3}]

Take[FindVertexColoring[G627],3]

GraphDataString

file=OpenAppend["~/exoo.m"]

WriteString[file,GraphDataString[G627,
"StandardName"->"ExooIsmailescuGraph627",
"Name"->"Exoo\[Hyphen]Ismailescu graph 627",
"Skip"->{"CliqueCoveringNumber","DominatingSet","TotalDominatingSet","VertexCover"},
TimeConstraint->5
]]

Close[file]

Embeddings

<<MathWorld`Graphs`

"ExooIsmailescuGraph19"

GraphData["ExooIsmailescuGraph19","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ExooIsmailescuGraph19","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["ExooIsmailescuGraph19"],#]&/@hc]]//Timing

quad

Planar

GraphData["ExooIsmailescuGraph19","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ExooIsmailescuGraph19","Circulant"]

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

Halin

GraphData["ExooIsmailescuGraph19","Halin"]

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

Rigid

GraphData["ExooIsmailescuGraph19","Rigid"]

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

Flexible

GraphData["ExooIsmailescuGraph19","Flexible"]

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

LCF

GraphData["ExooIsmailescuGraph19","LCF"]

GraphData["ExooIsmailescuGraph19","HamiltonianCycleCount"]

GraphData["ExooIsmailescuGraph19","LCFSignature"]

GraphData["ExooIsmailescuGraph19","LCFNotations"]

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

UnitDistance

GraphData["ExooIsmailescuGraph19","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["ExooIsmailescuGraph19","Matchstick"]

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

3D default

Graph3D[GraphData["ExooIsmailescuGraph19","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ExooIsmailescuGraph19","Polyhedral"]

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

"ExooIsmailescuGraph19Core"

GraphData["ExooIsmailescuGraph19Core","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ExooIsmailescuGraph19Core","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

Length[bilat=Union@DeleteMissing[BilaterallyRotatedGraph@CircularEmbeddingFromHamiltonianCycle[GraphData["ExooIsmailescuGraph19Core"],#]&/@hc]]//Timing

Planar

GraphData["ExooIsmailescuGraph19Core","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ExooIsmailescuGraph19Core","Circulant"]

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

Halin

GraphData["ExooIsmailescuGraph19Core","Halin"]

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

Rigid

GraphData["ExooIsmailescuGraph19Core","Rigid"]

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

Flexible

GraphData["ExooIsmailescuGraph19Core","Flexible"]

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

LCF

GraphData["ExooIsmailescuGraph19Core","LCF"]

GraphData["ExooIsmailescuGraph19Core","HamiltonianCycleCount"]

GraphData["ExooIsmailescuGraph19Core","LCFSignature"]

GraphData["ExooIsmailescuGraph19Core","LCFNotations"]

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

UnitDistance

GraphData["ExooIsmailescuGraph19Core","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["ExooIsmailescuGraph19Core","Matchstick"]

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

3D default

Graph3D[GraphData["ExooIsmailescuGraph19Core","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ExooIsmailescuGraph19Core","Polyhedral"]

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

"ExooIsmailescuGraph40"

GraphData["ExooIsmailescuGraph40","StandardName"]

Primary

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

All

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

Inexact

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

Embedding types

GraphDataEmbeddings[GraphData["ExooIsmailescuGraph40","EdgeList"]]

Default embedding

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

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

RecognizeGraph[g]

Degenerate

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

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

Bilateral

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

Circular

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

Circular construction

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

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

Planar

GraphData["ExooIsmailescuGraph40","Planar"]

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

MinimalCrossing

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

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

MinimalCrossing construction

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

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

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

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

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

RecognizeGraph[g]

RectilinearCrossingCount[g]

Circulant

GraphData["ExooIsmailescuGraph40","Circulant"]

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

Halin

GraphData["ExooIsmailescuGraph40","Halin"]

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

Rigid

GraphData["ExooIsmailescuGraph40","Rigid"]

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

Flexible

GraphData["ExooIsmailescuGraph40","Flexible"]

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

LCF

GraphData["ExooIsmailescuGraph40","LCF"]

GraphData["ExooIsmailescuGraph40","HamiltonianCycleCount"]

GraphData["ExooIsmailescuGraph40","LCFSignature"]

GraphData["ExooIsmailescuGraph40","LCFNotations"]

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

UnitDistance

GraphData["ExooIsmailescuGraph40","UnitDistance"]

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

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

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

UnitDistance by refinement

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

UnitDistanceGraphEmbeddingQ[%]

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

Select[%,UnitDistanceGraphEmbeddingQ]

UnitDistance by FindUnitDistanceEmbedding

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

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

UnitDistance by FindSubgraphUnitDistanceEmbedding

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

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

Matchstick

GraphData["ExooIsmailescuGraph40","Matchstick"]

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

3D default

Graph3D[GraphData["ExooIsmailescuGraph40","Edges"]]

3D All

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

3D UnitDistance

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

3D Polyhedron

GraphData["ExooIsmailescuGraph40","Polyhedral"]

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

GraphData

GraphDataClassString

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