Dominant graphs for rectilinear network design with barriers

Dilip Chhajed, Udatta S. Palekar

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)255-263
Number of pages9
JournalIIE Transactions (Institute of Industrial Engineers)
Issue number4
StatePublished - 1997

ASJC Scopus subject areas

  • Industrial and Manufacturing Engineering


Dive into the research topics of 'Dominant graphs for rectilinear network design with barriers'. Together they form a unique fingerprint.

Cite this