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

By explicitly constructing the complete graph on n vertices, which has n(n-1)/2 edges, a rectilinear minimum spanning tree can be found using existing algorithms for finding a minimum spanning tree.

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.