# Rectilinear minimum spanning tree

In graph theory, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane (or more generally in–ℝd) is a minimum spanning tree of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.

## Applications

### Electronic design

The problem commonly arises in physical design of electronic circuits. In modern high-density integrated circuits wire routing is performed by wires which consist of segments running horizontally in one layer of metal and vertically in another metal layer. As a result, the wire length between two points is naturally measured with rectilinear distance. Although the routing of a whole net with multiple nodes is better represented by the rectilinear Steiner tree, the RMST provides a reasonable approximation and wire length estimate.[1]

## References

1. ^ F. K. Hwang. "On Steiner minimal trees with rectilinear distance." SIAM Journal of Applied Mathematics, 30:104–114, 1976.