On algorithm of numbering the spanning trees in a connected graph

Let $G = (V, E)$ be a finite connected graph without multiple edges or loops. We consider the task about the numbering of all the spanning trees of $G$. In [2, p. 180, p. 191] described a method of solution of this task, based on the properties of minors of an incidence matrix of $G$. In the same place (p. 191–193) gave algorithm of four Japanese mathematicians (Kasahara Y., Tezuka K., Ling Shun Tong, Kitahashi T., [6]), reduced the task to removal of brackets in the product of formal sums of edges of $G$. Here we concider the method based on lexicographical order on the set of all sequences of edges of $G$.
We will remind that a spanning tree $T$ of the graph $G$ is a tree consisting of edges of $G$ and connecting all the vertices of $G$.
We shall assume that $V =\{ 1,2, \ldots, n\} $, where $n$ is a number of vertices of $G$. If $a, b \in V$, then $ (a, b) $ will be designated the edge with end-points $a$ and $b$.
Let $T$ be a spanning in $G$. Then the set of his edges can be written in the form
\begin{equation} (a_1, b_1), (a_2, b_2), \ldots, (a_ {n-1}, b_ {n-1}), \tag{A} \end{equation}
where
\begin{equation} a_i<a_{i+1} \ {\rm or} \ a_i=a_{i+1}\ \text{and} \ b_i<b_{i+1}, \ \text{where}\ i=1,2,\ldots, n-2. \tag{B} \end{equation}

On a set of sequences of in the form of (A) with the additional condition (B) we will consider a lexicographic order. The smallest (with respect to this order) spanning tree will be the tree $T_0$ with edges $ (1,2)$, $(1,3)$, $ (1,4)$, $\ldots$, $ (1, n) $ provided $(1,b) \in E$ for $b=2,3, \ldots, n$. The greatest spanning tree $T_1$ will be $ (1, n) $, $ (2, n) $, $ (3, n) $, $\ldots$, $ (n-1, n) $ under a similar condition. Touching all sequences of a look (A) in ascending order between $T_0$ and $T_1$ and checking lack of cycles at the corresponding sets of edges, we will be able to get a list of all spanning trees.
We will give results of work of the appropriate computer program.
Example 1. For complite graph $K_n$ on $n$ vertices for $n\leq 9$ the lists of all the spanning trees are obtained. Due to Kely theorem $K_n$ has $n^{n-2}$ spanning trees. For $n=9$ thos number is equal $4\,782\,969$.
Example 2. Let $G$ be a graph on $12$ vertices in figure 1 (in the left). Then $G$ has $2\,415$ spanning trees.
Let $P$ be a finite set of points in the plane $R^2$. Then $G = (V, E) $ is a plane geometrical graph on top of $P$, if $V\subset R^2$ and egdes of $G$ are stright-line segments with the end-points in $P$ and two edges of $G$ intersects only in points of $P$ [3]. If $G$ is a tree and $V=P$, then $G$ called a spanning tree on top of $P$.
Example 3. Let $P$ be a set of square tops, and also its center. Then there are $45$ spanning trees on top of $P$.
Example 4. Let $P$ consists of square tops, and also middle of its parties. Then there are $3\ 273$ spanning trees on top of $P$.
Example 7. We will consider a set $P=L_{n,m}$ consisting of $n\cdot m$ points on the plane:
$$L_ { n, m } = \{ (i, j): i=1,2, \ldots, n, j=1,2, \ldots, m\}, $$
where $n, m\geq of 1$ are integers. Thus, $L_ { n, m } $ is a uniform lattice which points lie on $n$ horizontal straight lines and for $m$ vertical straight lines. The numbers $St(P)$ of a spanning trees on top of this lattice for small $n$ and $m$ it is specified in the following table:

At transfer the spanning trees it is possible to carry out a filtration. For example, it is possible to keep only those trees in the final list, which degrees of vertices not exceeded some number $r$. So, the complete graph on $8$ vertices has $8 ^6=262\,144$ spanning trees. Among them $201\ 600$ spanning trees which degree of vertices don't exceed $3 $, and $20\,160$ spanning trees with degree of vertices $\leq 2$.
Some modification of the main algorihm allows to receive the list of all crossing-free geometrical graph on top of $P$ [3]. For example, if $P$ consists of square tops, and also middle of its parties, the number of such a graph on top of $P$ is equal to $21\,795$ (this number included also the empty graph). If to add to $P$ the center of a square, this number will become to $167\,570$.
In work is considered also a task about creation of all triangulations of a finite set $P\subset R^2$. The algorithm of the solution of this task is available in [3]. The alternative description of algorithm of search is provided in this work.
Example 9. Let $P=L_{ n, m } $ be a uniform lattice on the plane (see example 7). Then the number $Tr(P)$ of triangulations of $L_{ n, m } $ for small $n$ and $m$ is specified in the following table: