The bottleneck 2-connected k-Steiner network problem for k ≤ 2

The geometric bottleneck Steiner network problem on a set of vertices X embedded in a normed plane requires one to construct a graph G spanning X and a variable set of k >= 0 additional points, such that the length of the longest edge is minimised. If no other constraints are placed on G, then a solution always exists which is a tree. In this paper, we consider the Euclidean bottleneck Steiner network problem for k <= 2, where G is constrained to be 2-connected. By taking advantage of relative neighbourhood graphs, Voronoi diagrams, and the tree structure of block cut-vertex decompositions of graphs, we produce exact algorithms of complexity O(n(2)) and O(n(2) log n) for the cases k = 1 and k = 2 respectively. Our algorithms can also be extended to other norms such as the L-p planes. (C) 2012 Elsevier B.V. All rights reserved.