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(2n) 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 z0 
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 z0 and direction East.
Sort all terminals to the right of a vertical line through z0 by their x-coordinate. Let Za be the list of sorted terminals that are above the horizontal line through z0 and let Zb be the corresponding list of terminals below this line. Consider the first terminal in Za 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 Zb; 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 z0 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 Zb. 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. Za. If we again get a non-empty lune and there are no more candidates in Zb 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(n2) 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.