Nauty Laman plugin

A plugin for the utility program geng provided with nauty that enables quick generation of nonisomorphic sparse and tight graphs. A graph is (k,l)-sparse if every subgraph with n > N vertices has at most kn-l edges and (k,l)-tight if it is (k,l)-sparse and has exactly kn-l edges.

Installation

1. Download and build nauty.
2. Clone this repo.
3. Provide the path to nauty using NAUTY_DIR, e.g., by modifying the makefile.
4. Run make.

To build the supplementary program filter_rank:

1. Download Eigen.
2. Provide the path to Eigen using EIGEN_DIR, e.g., by modifying the makefile.
3. Run make.

Usage

The compiled binary gensparseg adds a few new parameters to geng:

• -K#: generate (k,l)-tight graphs where l = k(k+1)/2. Minimum degree and number of edges will default to k and kn-l, respectively. Sparse graphs can be generated by manually providing the minimum and maximum number of edges (e.g. 0:999). In that case, the minimum degree will default to zero.
• -L#: provides the l when generating (k,l)-sparse or (k,l)-tight graphs.
• -H: generate (k,l)-tight graphs constructible by Henneberg type I moves. k defaults to 2 but can be set using -K#. l is always k(k+1)/2.
• -N#: all (complete graphs) graphs with this number of nodes or fewer are considered (tight) sparse. The default value is max(⌊k⌋,2) or the highest n such that a complete graph on n vertices satisfies the sparsity condition.

Both -K and -L accept rational numbers making it possible to generate, e.g., (3/2,2)-tight graphs (see results below). Note, however, that denominators equal to their numerator are ignored, e.g., -K2/2 is equivalent to -K2. If rational arguments are not needed, define the macro INT_KL before compiling for a small increase (~15% for some inputs) in performance.

Algorithm

For integers k and l satisfying 0 ≤ l < 2k and N ≤ k+1, the pebble game algorithm presented in Lee and Streinu (2008) Pebble game algorithms and sparse graphs is used. For all other cases, a naive method checking the sparsity of every subgraph is used. However, due to how geng generates the graphs, even this naive approach is fast.

Results - counts and execution times

The tables below show the execution time when generating graphs for various numbers of vertices n. All the tests were run on an AMD Ryzen Threadripper 3990X 64-Core Processor. Extensions to entries in OEIS are marked with (new).

Laman graphs

OEIS entry: A227117
Command: gensparseg $n -K2 -u

Laman graphs, minimally rigid graphs in 2D, are exactly the (2,3)-tight graphs.

n	11	12	13	14 (new)	15 (new)
Laman graphs	2 039 273	44 176 717	1 092 493 042	30 322 994 747	932 701 249 291
Execution time	1.8 s	42 s	20 min	10 h	15 days

Laman graphs constructible by Henneberg type I moves

OEIS entry: A273468
Command: gensparseg $n -H -u

n	12	13	14 (new)	15 (new)	16 (new)
H1 Laman graphs	23 352 425	498 028 767	11 836 515 526	310 152 665 647	8 883 427 573 134
Execution time	20 s	8.4 min	4.2 h	5.9 days	290 days*

* Total CPU time of 64 cores.

Bipartite Laman graphs

OEIS entry: A328060
Command: gensparseg $n -bK2 -u

n	15	16 (new)	17 (new)	18 (new)	19 (new)
Bipartite Laman graphs	17 860 267	293 210 063	5 277 557 739	103 177 250 918	2 174 556 695 546
Execution time	46 s	11 min	3.3 h	2.6 days	71 days*

* Total CPU time of 64 cores.

Geiringer graphs

OEIS entry: A328419
Command: gensparseg $n -K3 -u

Geiringer graphs, minimally rigid graphs in 3D, are exactly the (3,6)-tight graphs for n=1..7. For larger n, the former is a proper subset of the latter. The Geiringer graphs can be found by numerically checking the rigidity of the generated (3,6)-tight graphs using ./gensparseg $n -K3 | ./filter_rank -u.

n	6	7	8	9	10	11	12
(3,6)-tight graphs	4	26	375	11 495	613 092	48 185 341	5 116 473 573
Geiringer graphs	4	26	374	11 487	612 884	48 176 183	5 115 840 190*
Execution time				10 ms	740 ms	1.6 min	5.3 h

* Calculated by numerically checking the rigidity of the generated (3,6)-tight graphs.

(3/2,2)-tight graphs

OEIS entry: A233288
Command: gensparseg $n -K3/2L2 -u

Note that gensparseg can generate (3/2,2)-tight graphs also for odd orders n.

n	2	4	6	8	10	12	14	16	18 (new)
(3/2,2)-tight graphs	1	1	2	16	230	6 856	318 162	19 819 281	1 535 380 884
Execution time					10 ms	360 ms	39 s	1.9 h	20 days

Pseudoforests

OEIS entry: A134964
Command: gensparseg $n 0:999 -K1L0 -u

Pseudoforests are the (1,0)-sparse graphs.

n	15	16	17	18	19	20	21
Pseudoforests	282 693	793 697	2 237 982	6 335 978	17 992 622	51 235 887	146 228 734
Execution time	2.1 s	8.0 s	32 s	2.2 min	9.6 min	43 min	3.2 h

Trees

OEIS entry: A000055
Command: gensparseg $n -K1 -u

Trees, minimally rigid graphs in 1D, are exactly the (1,1)-tight graphs. Note that this is a terribly inefficient way of generating trees, consider instead the nauty program gentreeg.

n	17	18	19	20	21	22	23
Trees	48 629	123 867	317 955	823 065	2 144 505	5 623 756	14 828 074
Execution time	2.4 s	9.5 s	40 s	2.8 min	12 min	54 min	4.4 h