The space of parallel linear networks with a~fixed boundary

A. O. Ivanov ; A. A. Tuzhilin

Izvestiya. Mathematics , Tome 63 (1999) no. 5, pp. 923-962.

Résumé

In this paper we study the structure of the set $[G,\varphi]_\Gamma$ of immersed linear networks in $\mathbb R^N$ that are parallel to a given immersed linear network $\Gamma\colon G\to\mathbb R^N$ and whose boundary $\varphi$ coincides with the boundary of $\Gamma$. We prove that $[G,\varphi]_\Gamma$ is a convex polyhedral subset in the configuration space of moving vertices of the graph $G$. We also calculate the dimension of this convex subset and estimate the number of its faces of maximal dimension. The results obtained are used to describe the space of all locally minimal (weighted minimal) networks in $\mathbb R^N$ with a fixed topology and a fixed boundary. In the case of planar networks in which the degrees of vertices are at most three (Steiner networks), this dimension is calculated in topological terms.

Bibliographie

[1] Clark R. C., “Communication networks, soap films and vectors”, Phys. Ed., 16 (1981), 32–37 | DOI

[2] Dijkstra E. W., “A note on two problems with connection with graphs”, Numer. Math., 1:5 (1959), 269–271 | DOI | MR | Zbl

[3] Du D. Z., Hwang F. K., “A New Bound for the Steiner Ratio”, Trans. Amer. Math. Soc., 278:1 (1983), 137–148 | DOI | MR | Zbl

[4] Du D. Z., Hwang F. K., A Proof of Gilbert–Pollak's Conjecture on the Steiner Ratio, Preprint DIMACS Technical Report No 90–72, 1990 | MR

[5] Du D. Z., Hwang F. K., “An approach for proving lower bounds: solution of Gilbert–Pollak's Conjecture on the Steiner Ratio”, Proc of the 31st annual symp. on found. of comp. science (1990)

[6] Du D. Z., Hwang F. K., Chao S. C., “Steiner minimal trees for points on a circle”, Proc. Amer. Math. Soc., 95:4 (1985), 613–618 | DOI | MR | Zbl

[7] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for points on a zig-zag lines”, Trans. Amer. Math. Soc., 278:1 (1983), 149–156 | DOI | MR | Zbl

[8] Du D. Z., Hwang F. K., Weng J. F., “Steiner minimal trees for Regular Polygons”, Disc. and Comp. Geometry, 2 (1987), 65–84 | DOI | MR | Zbl

[9] Du D. Z., Hwang F. K., Yao E. N., “The Steiner ratio conjecture is true for five points”, J. Combin Th. Ser. A38, 1985, 230–240 | MR | Zbl

[10] Du D. Z., Hwang F. K., Song G. D., Ting G. T., “Steiner minimal trees on sets of four points”, Discr. and Comp. Geometry, 2 (1987), 401–414 | DOI | MR | Zbl

[11] Garey M. R., Johnson D. S., “The complexity of computing Steiner minimal trees”, SIAM J. Algebraic Discrete Methods, 32 (1977), 835–859 | MR | Zbl

[12] Garey M. R., Graham R. L., Johnson D. S., “Some $NP$-complete geometric problems”, Eighth Annual Symp. on Theory of Comput., 1976, 10–22 | MR | Zbl

[13] Gilbert E. N., Pollak H. O., “Steiner minimal trees”, SIAM J. Appl. Math., 16:1 (1968), 1–29 | DOI | MR | Zbl

[14] Hildebrandt S., Tromba A., Mathematics and optimal form, Scientific American Books, Inc., New York, 1984 | MR

[15] Hwang F. K., “A linear time algorithm for full Steiner trees”, Oper. Res. Letter, 5 (1986), 235–237 | DOI | MR

[16] Hwang F. K., Weng J. F., “Hexagonal coordinate Systems and Steiner minimal trees”, Disc. Math., 62 (1986), 49–57 | DOI | MR | Zbl

[17] Hwang F. K., Richards D., Winter P., The Steiners Tree Problem, Elsevier Science Publishers, 1992 | MR

[18] Jarnik V., Kössler M., “O minimalnich grafeth obeahujicich n danijch bodu”, Cas. Pest. Mat. a Fys., 63 (1934), 223–235 | Zbl

[19] Kruskal J. B., “On the shortest spanning subtree of a graph and traveling salesman problem”, Proc. Amer. Math. Soc., 7 (1956), 48–50 | DOI | MR | Zbl

[20] Melzak Z. A., “On the problem of Steiner”, Canad. Math. Bull., 4 (1960), 143–148 | MR

[21] Melzak Z. A., Companion to concrete mathematics, Wiley-Interscience, N. Y., 1973 | MR | Zbl

[22] Pollak H. O., “Some remarks on the Steiner problem”, J. Combin. Thy. Ser. A24, 1978, 278–295 | DOI | MR | Zbl

[23] Preparata F., Shamos M., Computational Geometry. An introduction, Springer-Verlag, N. Y., 1985 | MR

[24] Prim R. C., “Shortest connecting networks and some generalizations”, BSTJ, 36 (1957), 1389–1401

[25] Rubinstein J. H., Thomas D. A., “The Steiner ratio conjecture for six points”, J. Combin. Thy. Ser. A58, 1989, 54–77 | MR

[26] Rubinstein J. H., Thomas D. A., Steiner Minimal Networks for Convex Configurations, Preprint Univ. Melbourne. Dep. of Math. series No 15 –1991 | MR

[27] Rubinstein J. H., Thomas D. A., “Graham's Problem On Shortest Networks for Points on a Circle”, Algorithmica, 7 (1992), 193–218 | DOI | MR | Zbl

[28] Shamos M. I., Computational Geometry, Ph. D. Thesis, Dept. of Comput. Sci., Yale Univ., 1978 | Zbl

[29] Smith W. D., “How to find Steiner minimal trees in Euclidean $d$-space”, Algorithmica, 1992, no. 7, 137–177 | DOI | MR

[30] Emelichev V. A. i dr., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[31] Dao Chong Tkhi, Fomenko A. T., Minimalnye poverkhnosti i problema Plato, Nauka, M., 1987 | MR | Zbl

[32] Fomenko A. T., Topologicheskie variatsionnye zadachi, Izd-vo MGU, M., 1984 | MR | Zbl

[33] Fomenko A. T., Variatsionnye metody v topologii, Nauka, M., 1982 | MR

[34] Tuzhilin A. A., Fomenko A. T., Elementy geometrii i topologii minimalnykh poverkhnostei, Nauka, M., 1991 | MR

[35] Ivanov A. O., “Geometriya ploskikh lokalno minimalnykh binarnykh derevev”, Matem. sb., 186:9 (1995), 45–76 | MR | Zbl

[36] Ivanov A. O., “Ploskie vzveshennye minimalnye binarnye derevya”, Fundamentalnaya i prikladnaya matem., 2:2 (1996), 511–562 | MR

[37] Ivanov A. O., Tuzhilin A. A., “Reshenie zadachi Shteinera dlya vypuklykh granits”, UMN, 45:2 (1990), 207–208 | MR | Zbl

[38] Ivanov A. O., Tuzhilin A. A., “Zadacha Shteinera dlya vypuklykh granits ili ploskie minimalnye seti”, Matem. sb., 182:12 (1991), 1813–1844 | MR

[39] Ivanov A. O., Tuzhilin A. A., “Geometriya minimalnykh setei i odnomernaya problema Plato”, UMN, 47:2 (1992), 53–115 | MR | Zbl

[40] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. I: general case”, Advances in Soviet Mathematics, 15 (1993), 15–92 | MR | Zbl

[41] Ivanov A. O., Tuzhilin A. A., “The Steiner problem for convex boundaries. II: the regular case”, Advances in Soviet Mathematics, 15 (1993), 93–131 | MR | Zbl

[42] Ivanov A. O., Tuzhilin A. A., Minimal Networks. The Steiner Problem and Its Generalizations, CRC Press, Boca Raton, 1994 | MR | Zbl

[43] Ivanov A. O., Tuzhilin A. A., “Topologii lokalno minimalnykh ploskikh binarnykh derevev”, UMN, 49:6 (1994), 191–192 | MR | Zbl

[44] Ivanov A. O., Tuzhilin A. A., “Vzveshennye minimalnye $2$-derevya”, UMN, 50:3 (1995), 155–156 | MR | Zbl

[45] Ivanov A. O., Tuzhilin A. A., “Geometriya ploskikh lineinykh derevev”, UMN, 51:2 (1996), 161–162 | MR | Zbl

[46] Ivanov A. O., Tuzhilin A. A., “Chislo vrascheniya ploskikh lineinykh derevev”, Matem. sb., 187:8 (1996), 41–92 | MR | Zbl

[47] Ivanov A. O., Tuzhilin A. A., “Geometriya mnozhestva minimalnykh setei dannoi topologii s fiksirovannoi granitsei”, Izv. RAN. Ser. matem., 61:6 (1997), 119–152 | MR | Zbl

[48] Ivanov A. O., Iskhakov I. V., Tuzhilin A. A., “Minimalnye seti na pravilnykh mnogougolnikakh: realizatsiya lineinykh parketov”, Vest. MGU. Ser. matem., 1993, no. 6, 77–81 | MR

[49] Ivanov A. O., Ptitsyna I. V., Tuzhilin A. A., “Klassifikatsiya zamknutykh minimalnykh setei na ploskikh dvumernykh torakh”, Matem. sb., 183:12 (1992), 3–44 | MR | Zbl

[50] Tuzhilin A. A., “Minimalnye binarnye derevya s pravilnoi granitsei: sluchai skeletov s chetyrmya kontsami”, Matem. sb., 187:4 (1996), 117–159 | MR | Zbl

[51] Tuzhilin A. A., “Minimalnye binarnye derevya s pravilnoi granitsei: sluchai skeletov s pyatyu kontsami”, Matem. zametki, 61:6 (1997), 907–921 | MR | Zbl

[52] Kuhn H. W., “Steiner's problem revisted”, Studies in Optimization, Studies in Math., 10, eds. G. B. Dantzig, B. C. Eaves, Math. Assoc. Amer., 1975, 53–70 | MR

[53] Zacharias M., Encyklopädie der Mathematischen Wissenschaften, V. III. AB9