In this section we give a description of the currently most efficient method for solving Rectiliniear Steiner Tree Problems to optimality. We will use the fact that there exists an SMT which is a union of FSTs having Hwang-topology.

The idea is simply to generate all Hwang-topology FSTs that fulfill certain necessary optimality conditions, in particular
those given in the previous section. This may a first seem to be an hopelessly inefficient approach since we (in principle)
have to consider all O(2^{n}) subsets of terminals; however most subsets are only considered implicitly and very few
(i.e., approximately linear in the number of terminals) FSTs survive all the conditions in practice. After this first FST
generation phase we need to select a subset of the generated FSTs that interconnect all terminals and have minimum total
length. This second phase is called FST concatenation and it turns out to be the computationally hardest task of the two phases.
It is covered in Concatenation.

Assume that some terminal z_{0} Z is the root of a Hwang-topology FST. The long leg has one of four possible directions: North, East, South or West.
Let us consider a specific direction, say East. This situation is shown in the FST Generation visualizations.
Let us (informally) describe a procedure for generating all FSTs having root z_{0} and direction East.

Sort all terminals to the right of a vertical line through z_{0} by their x-coordinate.
Let Z_{a} be the list of sorted terminals that are above the horizontal line through z_{0} and let Z_{b}
be the corresponding list of terminals below this line. Consider the first terminal in Z_{a} and connect it to the
root as shown, that is, create a segment along the long leg and another one connecting the terminal to the long leg.
Now we may test whether this partial FST can be a subtree in some possibly larger FST. This is done by applying several necessary
optimality conditions, including those given in the previous section.

In the examples in the visualization, we only show the effect of applying the empty lune condition (Lemma 3.2). When both lunes are empty we save the partial FST and continue growing the FST. This is done by choosing the next terminal from Z_{b}; recall that the terminals must alternate along the long leg.
As long as all necessary optimality conditions are fulfilled, we recurse until all FSTs having z_{0} as root and long leg direction East are generated (note that we also need to consider the case where the first terminal is chosen from Z_{b}. The algorithm is repeated for all combinations of terminals and directions.
In case a non-empty lune appears; this means that this partial FST cannot be a subtree in some larger FST. Therefore, we skip this terminal and choose the next candidate from i.e. Z_{a}.
If we again get a non-empty lune and there are no more candidates in Z_{b} we backtrack, i.e., choose another candidate for the previous terminal.

This procedure only generates type (i) FSTs, but type (ii) FSTs can be generated simultaneously. Here we need to try all possibilities of attaching a single terminal to the last vertical segment.

An FST-independent preprocessing phase which runs in O(n^{2}) time can be used to speed up this FST growing algorithm significantly in practice.
In fact, for most problem instances the preprocessing dominates the total running time even if the second part is the one that requires exponential time in
the worst-case. A well-tuned implementation of this algorithm [GeoSteiner] generates the FSTs for a randomly generated 1000 terminal instance in less than one second;
the number of FSTs surviving all tests is approximately 4n.

This set of FSTs includes n-1 edges from an MST for Z, which may be considered as the 2-terminal FSTs.

Text and examples based on: