Dominant graphs for rectilinear network design with barriers

Given a set of points on a Cartesian plane and the coordinate axes, the rectilinear network design problem is to find a network, with arcs parallel to either one of the axes, that minimizes the fixed and the variable costs of interactions between a specified set of pairs of points. We show that, even in the presence of arbitrary barriers, an optimal solution to the problem (when feasible) is contained in a grid graph defined by the set of given points and the barriers. This converts the spatial problem to a combinatorial problem. Finally we show connections between the rectilinear network design problem and a number of well-known problems. Thus this paper unifies the known dominating set results for these problems and extends the results to the case with barriers.