Brazil, M.; Rubinstein, J. H.; Thomas, D. A.; Weng, J. F.; Wormald, N. C. Gradient-constrained minimum networks. I: Fundamentals. (English) Zbl 1068.90605 J. Glob. Optim. 21, No. 2, 139-155 (2001). Summary: In three-dimensional space an embedded network is called gradient-constrained if the absolute gradient of any differentiable point on the edges in the network is no more than a given value \(m\). A gradient-constrained minimum Steiner tree \(\tau\) is a minimum gradient-constrained network interconnecting a given set of points. In this paper we investigate some of the fundamental properties of these minimum networks. We first introduce a new metric, the gradient metric, which incorporates a new definition of distance for edges with gradient greater than \(m\). We then discuss the variational argument in the gradient metric, and use it to prove that the degree of Steiner points in \(\tau\) is either three or four. If the edges in \(\tau\) are labelled to indicate whether the gradients between their endpoints are greater than, less than, or equal to \(m\), then we show that, up to symmetry, there are only five possible labellings for degree 3 Steiner points in \(\tau\). Moreover, we prove that all four edges incident with a degree 4 Steiner point in \(\tau\) must have gradient \(m\) if \(m\) is less than 0.38. Finally, we use the variational argument to locate the Steiner points in \(\tau\) in terms of the positions of the neighbouring vertices. Cited in 1 ReviewCited in 13 Documents MSC: 90C35 Programming involving graphs or networks 05C35 Extremal problems in graph theory 90B10 Deterministic network models in operations research × Cite Format Result Cite Review PDF Full Text: DOI