Optimal Interconnection Trees in the Plane

Let A, B, and C be three points in the plane. What graph G has the property that its edges connect these three points and the length of these edges is minimal? Clearly, G will be a tree, but which tree? The book starts with this classical problem and its beautiful solution, (which is a special case of a Euclidean minimum Steiner tree), then works its way to more general versions. What if there are more than three points, what if the cost of each edge is some function other than the length, and what if you must find the optimal graph G among the subgraphs of a given graph?

The problems are very intriguing, and their solutions, which are easy to read, make constant use of Euclidean geometry. This reviewer had a bit of a problem with the definitions, in that Minimum Steiner Trees are defined before Steiner Trees. There are some interesting illustrations, like the figure on page 8 that shows the Euclidean minimum Steiner trees of 2741 cities in Denmark, using the software package GeoSteiner.

The only weak point in the book is the exercises: there only about 12 of them per chapter. None of them come with solutions. That is a missed opportunity to show the reader that this beautiful theory has a large and diverse set of applications.

Miklós Bóna is Professor of Mathematics at the University of Florida.