A *Halin graph* is a graph constructed by embedding a tree with no vertex of degree
two in the plane and then adding a cycle to join the tree’s leaves.


We found a list of the number of Halin graphs within $14$ vertices on the website <https://oeis.org/A346779>.



```
n       a(n)
1       0
2       0
3       0
4       1
5       1
6       2
7       2
8       4
9       6
10      13
11      22
12      50
13      106
14      252

```

It seems that there aren't many Halin graphs with at most 14 vertices (252 Halin graphs with 14 vertices is considered quite a small number).  

Based on this, I estimate that the number of non-isomorphic Halin graphs within 20 vertices may also not be too large.


By [Wiki](https://en.wikipedia.org/wiki/Halin_graph), it is possible to test whether a given $n$-vertex graph is a Halin graph in linear time. To obtain Halin graphs with more vertices, such as a Halin graph with 20 vertices, one approach could be to generate 3-connected planar graphs with 20 vertices first and then filter them one by one. However, the problem is that the number of [3-connected planar graphs](https://oeis.org/A000944) with 20 vertices is astronomically large. Therefore, I wonder if there is an algorithm generating Halin graphs or existing graph data available (I haven't found it either).



Is there an algorithm to generate non-isomorphic Halin graphs?
There is a theorem due to Jordan which is useful for enumerating or generating trees: every tree has a centre or a bicentre. To enumerate/generate suitable bicentral trees, enumerate/generate suitable rooted trees grouping them by height and join two rooted trees of the same height with an edge between their roots. To enumerate/generate suitable central trees, enumerate/generate suitable rooted trees grouping them by height and join two or more to the centre by their roots, ensuring that the maximum height of the trees chosen is not unique.


This construction method also gives a natural way to generate the embeddings into the plane.


