LOW-DEGREE MINIMUM SPANNING-TREES

Motivated by practical VLSI routing applications, we study the maximum vertex degree of a minimum spanning tree (MST). We prove that, under the L(p) norm, the maximum vertex degree over all MSTs is equal to the Hadwiger number of the corresponding unit bail; we show an even tight er bound for MSTs where the maximum degree is minimized. We give the b est-known bounds for the maximum MST degree for arbitrary L(p) metrics in all dimensions, with a focus on the rectilinear metric in two and three dimensions. We show that for any finite set of points in the rec tilinear plane an MST exists with maximum degree of at most 4, and for three-dimensional rectilinear space the maximum possible degree of a minimum-degree MST is either 13 or 14.