The geometry of minimal networks with a~given topology and a~fixed boundary

A. O. Ivanov ; A. A. Tuzhilin

Izvestiya. Mathematics , Tome 61 (1997) no. 6, pp. 1231-1263.

Résumé

In this paper we study the structure of the set $\mathcal M_G(\varphi)$ of all locally minimal plane networks with a fixed topology $G$ and a fixed boundary $\varphi$. It is shown that if this set is non-empty, then it is a $k$-dimensional convex body in the configuration space $\mathbb R^N$ of the movable vertices of the network, where $k$ is the cyclomatic number for the movable subgraph in $G$. In particular, all the networks in $\mathcal M_G(\varphi)$ are parallel, have the same length, and can be deformed into one another in the class of locally minimal networks of the same type and with the same boundary. Moreover, we describe how two networks belonging to $\mathcal M_G(\varphi)$ can be distinguished.

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, DIMACS Technical Report No 90–72, 1990

[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. A, 38 (1985), 230–240 | DOI | 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., Graham R. L., Johnson D. S., “Some $NP$-complete geometric problems”, Eighth Annual Symp. on Theory of Comput., 1976, 10–22 | DOI | MR | Zbl

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

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

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

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

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

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

[18] 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

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

[20] Melzak Z. A., Companion to concrete mathematics, Wiley–Interscience, New York, 1973 | MR | Zbl

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

[22] Preparata F., Shamos M., Computational Geometry. An introduction, Springer-Verlag, New York, 1985 | MR

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

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

[25] Rubinstein J. H., Thomas D. A., Cole T., Steiner Minimal Networks for Convex Configurations, Preprint series No 15, The university of Melbourne dept. of Math., 1991 | MR

[26] 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

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

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

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

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

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

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

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

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

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

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

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

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

[39] 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

[40] 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

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

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

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

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

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

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

[47] 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

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

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

[50] 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

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