Dominant graphs for rectilinear network design with barriers. BEBR 92-0143
Dilip Chhajed, Udatta S. Palekar · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1992
Given a set of points on a Cartesian plane and the coordinate axes, the rectilinear network design problem is to find a network, with sides parallel and perpendicular to the axes, which 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 barriers, an optimal solution to the problem 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.