Rubinstein, J. H.; Thomas, D. A.; Wormald, N. C. Steiner trees for terminals constrained to curves. (English) Zbl 0869.05023 SIAM J. Discrete Math. 10, No. 1, 1-17 (1997). Summary: We give a polynomial time algorithm for solving the Euclidean Steiner tree problem when the terminals are constrained to lie on a fixed finite set of disjoint finite-length compact simple smooth curves. The problem is known to be NP-hard in general. We also show it to be NP-hard if the terminals lie on two parallel infinite lines or on a bent line segment provided the bend has an angle of less than \(120^\circ\). Cited in 1 ReviewCited in 11 Documents MSC: 05C05 Trees 90B85 Continuous location 68R10 Graph theory (including graph drawing) in computer science Keywords:polynomial time algorithm; Euclidean Steiner tree; curves; NP-hard × Cite Format Result Cite Review PDF Full Text: DOI