Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications

Preface.- 1 Euclidean and Minkowski Steiner Trees.- 1.2 Algorithms for a given Steiner topology.- 1.3 Global properties of minimum Steiner trees.- 1.4 GeoSteiner algorithm.- 1.5 Efficient constructions for special terminal sets.- 1.6 Steiner trees in Minkowski planes.- 1.7 Applications and extensions.- 2 Fixed Orientation Steiner Trees.- 2.1 Fixed orientation networks.- 2.2 Local properties for Steiner points.- 2.3 Local properties for full components.- 2.4 Algorithms for a given topology.- 2.5 Global properties of minimum Steiner trees.- 2.6 GeoSteiner algorithm.- 2.7 Applications and extensions.- 3 Rectilinear Steiner Trees.- 3.1 Local properties for Steiner points and full components.- 3.2 Global properties for minimum Steiner trees.- 3.3 GeoSteiner algorithm.- 3.4 FLUTE algorithm.- 3.5 Efficient constructions for special terminal sets.- 3.6 Applications and extensions.- 4 Steiner Trees with Other Costs and Constraints.- 4.1 The gradient-constrained Steiner tree problem.- 4.2 Obstacle-avoiding Steiner trees.- 4.3 Bottleneck and general k-Steiner tree problems.- 4.4 Trees Minimizing Flow Costs.- 4.5 Related topics.- 5 Steiner Trees in Graphs and Hypergraphs.- 5.1 Steiner trees in graphs.- 5.2 Minimum spanning trees in hypergraphs.- 5.3 Steiner trees in hypergraphs.- A Appendix.