3. Rectilinear Steiner Trees

The more general definition of a cross, for any norm, is given in Sect. 1.​6.​2 Clearly, the definition in this chapter is consistent with the more general definition.

The Hwang form is named after Frank K. Hwang, who gave the characterisation in his seminal paper from 1976 [209]. A simpler proof of the Hwang form was given by Richards and Salowe [322] (see also Zachariasen [429]). In this book we give a proof that is based on the theory of canonical forms developed for general fixed orientation metrics in Chap. 2.

One of the first probabilistic bounds on the number of full components was given by Salowe and Warme [332] in 1995. They showed that for a set of randomly and uniformly distributed terminals, the expected number of full components spanning k terminals, where k is a constant, is O(n ²). Also, for \(k = \Omega (n)\) they proved that the expected number of full components spanning k terminals is O(1). Zachariasen [427] showed that the expected number of full components spanning k terminals, and satisfying the rectangle property and a simplified bottleneck Steiner distance property, is O(n(loglogn) ^k−2). Finally, Fößmeier and Kaufmann [155] showed that the expected number of full components satisfying the tree star property is \(O(n \cdot 2^{\sqrt{n\log n}})\) with high probability.

The first computer code to compute minimum rectilinear Steiner trees appears to have been developed by Yang and Wing [421] in 1971. The algorithm used a reduction to the Hanan grid, and solved the graph problem using a branch-and-bound algorithm for graphs. The largest solved problem had 9 terminals, and it was solved on a reduced Hanan grid with 20 vertices and 31 edges – pruned using a path-convex hull approach. In a follow-up paper from 1972, Yang and Wing [422] mentioned that by using the Dreyfus and Wagner dynamic programming algorithm [131], it should be possible to solve problems with 14 terminals in a couple of minutes, but problems with 18 terminals would require more than a day of computing time. In 1989, Sirodenko [348] presented an approach that allowed problems with up to 11 terminals to be solved. In the early 1990s, a number of papers appeared. Ganley and Cohoon [161] presented a dynamic programming algorithm that made it possible to solve problems with up to 16 terminals; an improved FST-based dynamic programming algorithm increased the range to 18 terminals [162]. Using a considerable engineering effort, Thomborson et al. [366] managed to solve problem instances with up to 23 terminals. Shortly after, Salowe and Warme [332] suggested a GeoSteiner approach, allowing the solution of problem instances with more than 30 terminals; Hetzel [195] pushed the range to 50 terminals. The real breakthrough occurred a few years later when Warme [386] in 1998 computed minimum rectilinear Steiner trees for problem instances with more than 1,000 terminals.

In addition to the references to the primary sources given in this section, more details on some of the results discussed here can also be found in Part III, Chapter 3 of Hwang et al. [211] and in the survey article of Thomas and Weng [364].

A classical paper on the physical layout of circuits, including the design of printed circuit boards, is that of Soukup [356]. A more recent overview of mathematical methods for the physical layout of printed circuit boards can be found in [1].

The literature on the physical design of integrated circuits is vast. Some fairly recent books and theses include – in chronological order – Lengauer [249], Kahng and Robins [229], Pecht and Wong [301], Sarrafzadeh and Wong [339], Gerez [173], Sait and Youssef [331], Sherwani [347], Vygen [378], Saxena et al. [340] and Kahng et al. [226]. Some early contributions on the routing problem are Yang and Wing [423] and Hightower [196]; more recent surveys can be found in Möhring et al. [284], Cong et al. [118], Peyer [303], Moffitt et al. [283], Moffitt [282], Müller [286], Robins and Zelikovsky [325], Alpert et al. [10] and Gester et al. [175]. The list of combinatorial problems in chip design recently compiled by Korte and Vygen [238] illustrates the challenges in the field. The authors consider the chip design problem to be one of the most important application areas in (discrete) mathematics. In particular, efficient algorithms are needed to handle problems with millions of modules and nets.