Rectilinear minimum spanning tree
Encyclopedia
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.
of electronic circuits. In modern high-density integrated circuit
s 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, the rectilinear minimum spanning tree (RMST) of a set of n points in the plane
Plane (mathematics)
In mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
(or more generally in–ℝd) is a minimum spanning tree
Minimum spanning tree
Given a connected, undirected graph, a spanning tree of that graph is a subgraph that is a tree and connects all the vertices together. A single graph can have many different spanning trees...
of that set, where the weight of the edge between each pair of points is the rectilinear distance between those two points.
Electronic design
The problem commonly arises in physical designPhysical design (electronics)
In integrated circuit design, physical design is a step in the standard design cycle which follows after the circuit design. At this step, circuit representations of the components of the design are converted into geometric representations of shapes which, when manufactured in the corresponding...
of electronic circuits. In modern high-density integrated circuit
Integrated circuit
An integrated circuit or monolithic integrated circuit is an electronic circuit manufactured by the patterned diffusion of trace elements into the surface of a thin substrate of semiconductor material...
s wire routing
Routing (EDA)
In electronic design, wire routing, commonly called simply routing, is a step in the design of printed circuit boards and integrated circuits . It builds on a preceding step, called placement, which determines the location of each active element of an IC or component on a PCB...
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
Rectilinear Steiner tree
The rectilinear Steiner tree problem, minimum rectilinear Steiner tree problem , or rectilinear Steiner minimum tree problem is a variant of the geometric Steiner tree problem in the plane, in which the Euclidean distance is replaced with the rectilinear distance...
, the RMST provides a reasonable approximation and wire length estimate.