Mixed spanning trees: a technique for performance-driven routing

Presents a new strategy for performance-driven global routing. This strategy focuses on the creation of spanning trees whose properties are under the control of the designer. The authors use it to construct a spanning tree with simultaneous, provable performance guarantees on total length, single-source shortest path length, and bottleneck path length. For rectilinear problems on n terminals in the plane, such a tree can be constructed in O(n log n) time