<<"LamanGraphs.m";

LamanGraphs   —   Copyright © 2016   Christoph Koutschan
This program comes with absolutely no warranty; it is free software,
and you are welcome to redistribute it and/or modify it under the
terms of the GNU General Public License (http://www.gnu.org/licenses/).

Generate and Count Laman Graphs

TableForm[Table[Timing[Length[LamanGraphs[n]]],{n,3,10}]]

TableForm[Table[Timing[Length[H1LamanGraphs[n]]],{n,3,10}]]

(* Number of Laman graphs of size n *)
numLG={1,1,1,1,3,13,70,608,7222,110132,2039273,44176717};

(* Number of Laman graphs that use only H1 moves *)
numH1={1,1,1,1,3,11,61,499,5500,75635,1237670,23352425};

N[numH1/numLG]

ListPlot[%]

Number of Embeddings

(* Number of embeddings - computed with Groebner basis approach *)
Do[Print["Embs["<>ToString[n]<>"] = ",NumberOfEmbeddings/@LamanGraphs[n]],{n,3,6}];

(* Number of embeddings - computed with our algorithm *)
Do[Print["Embs["<>ToString[n]<>"] = ",Embs[n]=LamanNumber/@LamanGraphs[n]],{n,3,6}];

TableForm[Table[Timing[Max[Embs[n]=LamanNumber/@LamanGraphs[n]]],{n,3,10}]]

Sort[Tally[Embs[7]]]

Sort[Tally[Embs[8]]]

Sort[Tally[Embs[9]]]

Sort[Tally[Embs[10]]]

Graph with Maximal Embedding Number

Do[
MaxEmbGraph[n]=LamanGraphs[n][[Position[Embs[n],Max[Embs[n]]][[1,1]]]];
Print["MaxEmbGraph[",n,"] = ",G2Edges[MaxEmbGraph[n]]];
,{n,6,10}];

(* Compare runtime of combinatorial algorithm with Groebner approach, *)
(* using, for each n, the graph with the largest number of embeddings. *)
Do[
Print["n = "<>ToString[n]<>":"];
Print["  Algorithm: ",Timing[LamanNumber[MaxEmbGraph[n]]]];
Print["  Groebner: ",Timing[NumberOfEmbeddings[MaxEmbGraph[n]]]];
,{n,6,9}];

Timing[LamanNumber[MaxEmbGraph[10]]]

Computation Trees

comp3=LN[G2Edges[7]]

TreeForm[comp3,ImageSize->1200]

TreeForm[comp3/.L[G1_,G2_]->L[Graph[G1],Graph[G2]]]

LN[G2Edges[LamanGraphs[4][[1]]]]

TreeForm[%]