×

Geometry and topology of local minimal 2-trees. (English) Zbl 0888.05014

A planar binary tree is a tree in the plane all of whose vertices have degree 1 or 3; minimum Steiner trees having no vertex of degree 2 are trees of that kind. For such a tree \(\Gamma\) the authors define a twisting number \(\text{tw }\Gamma\) as follows: The twisting number of a directed path in \(\Gamma\) is the difference between the number of left-hand branchings and the number of right-hand branchings along that path, and then \(\text{tw }\Gamma\) is the maximum of the twisting numbers of all directed paths. Finally, a finite point set \(M\) is said to have \(k\) convexity levels iff \(M\) is the disjoint union of \(M_1,\dots, M_k\) where \(M_j\) \((j= 1,\dots,k)\) is the set of those points of \(M_j\cup\cdots\cup M_k\) which are lying on the boundary of the convex hull of this set. Now, the authors’ main result says that the twisting number of a planar binary minimum Steiner tree spanning a set \(M\) that has \(k\) convexity levels is bounded by \(12(k- 1)+5\) and this bound is best possible. This generalizes earlier results of the authors concerning the case \(k=1\). The main part of the lengthy paper is devoted to the investigation of the twisting number by considering analoguous notions for general polygonal lines.

MSC:

05C05 Trees
05C35 Extremal problems in graph theory
57M15 Relations of low-dimensional topology with graph theory
52A10 Convex sets in \(2\) dimensions (including convex curves)
Full Text: DOI

References:

[1] J. B. Kruskal, On the shortest spanning subtree of a graph and traveling salesman problem. Proc. Amer. Math. Soc., 1956, vol. 7, pp. 48-50. · Zbl 0070.18404 · doi:10.1090/S0002-9939-1956-0078686-7
[2] R. C. Prim, Shortest connecting networks and some generalizations. BSTJ, 1957, vol. 36, pp. 1389-1401.
[3] E. W. Dijkstra, A note on two problems with connection with graphs. Numer. Math., 1959, vol. 1, no. 5, pp. 269-271. · Zbl 0092.16002 · doi:10.1007/BF01386390
[4] Z. A. Melzak, On the problem of Steiner. Canad. Math. Bull., 1960, vol. 4, pp. 143-148. · Zbl 0101.13201 · doi:10.4153/CMB-1961-016-2
[5] E. N. Gilbert and H. O. Pollak, Steiner minimal trees. SIAM J. Appl. Math., 1968, vol. 16, no. 1, pp. 1-29. · Zbl 0159.22001 · doi:10.1137/0116001
[6] D. Z. Du and F. K. Hwang, A New Bound for the Steiner Ratio. Trans. Amer. Math. Soc. 1983, vol. 278, no. 1, pp. 137-148. · Zbl 0523.51017 · doi:10.1090/S0002-9947-1983-0697065-3
[7] D. Z. Du, F. K. Hwang and J. F. Weng, Steiner minimal trees for points on a zig-zag lines. Trans. Amer. Math. Soc. 1983, vol. 278, no. 1, pp. 149-156. · Zbl 0523.51018 · doi:10.1090/S0002-9947-1983-0697066-5
[8] D. Z. Du, F. K. Hwang and S. C. Chao, Steiner minimal trees for points on a circle. Proc. Amer. Math. Soc., 1985, vol. 95, no. 4, pp. 613-618. · Zbl 0596.05022 · doi:10.1090/S0002-9939-1985-0810173-6
[9] D. Z. Du, F. K. Hwang and E. N. Yao, The Steiner ratio conjecture is true for five points. J. Combin Thy., Ser. A38, 1985, pp. 230-240. · Zbl 0576.05015 · doi:10.1016/0097-3165(85)90073-1
[10] F. K. Hwang, A linear time algorithm for full Steiner trees. Oper. Res. Letter, 1986, vol. 5, pp. 235-237. · Zbl 0582.05022 · doi:10.1016/0167-6377(86)90008-8
[11] F. K. Hwang and J. F. Weng, Hexagonal coordinate Systems and Steiner minimal trees. Disc. Math., 1986, vol. 62, pp. 49-57. · Zbl 0601.05016 · doi:10.1016/0012-365X(86)90040-3
[12] D. Z. Du, F. K. Hwang and J. F. Weng, Steiner minimal trees for Regular Polygons. Disc. and Comp. Geometry, 1987, vol. 2, pp. 65-84. · Zbl 0607.05022 · doi:10.1007/BF02187871
[13] D. Z. Du, F. K. Hwang, G. D. Song and G. T. Ting, Steiner minimal trees on sets of four points. Discr. and Comp. Geometry, 1987, vol. 2, pp. 401-414. · Zbl 0623.05013 · doi:10.1007/BF02187892
[14] Du D.Z., Hwang F.K., A Proof of Gilbert-Pollak’s Conjecture on the Steiner Ratio. DIMACS Technical Report, 1990, no. 90-72.
[15] 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.
[16] F. K. Hwang, D. Richards and P. Winter, The Steiners Tree Problem. Elsevier Science Publishers (to appear).
[17] E. J. Cockayne, On the Steiner problem. Canad. J. Math., 1967, vol. 10, pp. 431-450. · Zbl 0161.19203 · doi:10.4153/CMB-1967-041-8
[18] H. O. Pollak, Some remarks on the Steiner problem. J. Combin. Thy., Ser. A24, 1978, pp. 278-295. · Zbl 0392.05021 · doi:10.1016/0097-3165(78)90058-4
[19] R. C. Clark, Communication networks, soap films and vectors. Phys. Ed., 1981, vol. 16, pp. 32-37. · doi:10.1088/0031-9120/16/1/005
[20] J. H. Rubinstein and D. A. Thomas, The Steiner ratio conjecture for six points. J. Combin. Thy., Ser. A58, 1989, pp. 54-77. · Zbl 0739.05034 · doi:10.1016/0097-3165(91)90073-P
[21] W. D. Smith, How to find Steiner minimal trees in Euclideand-space. Algoritmica (to appear).
[22] A. L. Edmonds, J. H. Ewing and R. S. Kulkarni, Regular tesselations of surfaces and (p, q, 2)-triangle groups. Ann. Math., 1982, vol. 116, pp. 113-132. · Zbl 0497.57001 · doi:10.2307/2007049
[23] A. L. Edmonds, J. H. Ewing and R. S. Kulkarni, Torsion free subgroups of Fuchian groups and tesselations of surfaces. Inv. Math., 1982, vol. 69, pp. 331-346. · Zbl 0498.20033 · doi:10.1007/BF01389358
[24] Emel’ichev etc., Lections on Graphs Theory. Nauka, Moscow, 1990.
[25] A. T. Fomenko, The Plateau Problem. New York, Gordon and Breach Sc. Publ., 1989. · Zbl 0741.53005
[26] A. T. Fomenko, Variational problems in Topology. New York, Gordon and Breach Sc. Publ., 1990. · Zbl 0716.53004
[27] A.T.Fomenko and A.A.Tuzhilin, Elements of geometry and topology of minimal surfaces in three-dimensional space. AMS, 1992, vol. 93, Translations of Mathematical Monographs. · Zbl 0745.53001
[28] Z. A. Melzak, Companion to concrete mathematics. Wiley-Interscience, New York, 1973. · Zbl 0254.26003
[29] S. Hildebrandt and A. Tromba, Mathematics and optimal form. An imprint of Scientific American Books, Inc., New York, 1984.
[30] M. Zacharias, Encyklopädie der Mathematischen, Wissenschaften, vol. III AB9.
[31] H. W. Kuhn, Steiner’s problem revisted. In the book Studies in Optimization, ser. Studies in Math., vol. 10, Math. Assoc. Amer., edited by G. B. Dantzig and B. C. Eaves, 1975, pp. 53-70.
[32] V. Jarnik and M. Kössler, O minimalnich grafeth obeahujicich n danijch bodu. Cas. Pest. Mat. a Fys., 1934, vol. 63, pp. 223-235.
[33] F. Preparata and M. Shamos, Computational Geometry. An introduction. New York, Springer-Verlag, 1985. · Zbl 0575.68059
[34] A. O. Ivanov and A. A. Tuzhilin, Solution of the Steiner Problem for convex boundaries. Uspekhi. Mat. Nauk, 1990, vol. 45, no. 2, pp. 207-208, Russian. English transl. in Russian Math. Surveys (1990) · Zbl 0716.05025
[35] A. O. Ivanov and A. A. Tuzhilin, The Steiner problem for convex boundaries or flat minimal networks. Matem. Sbornik, 1991, vol. 182, no. 12, pp. 1813-1844. Russian. · Zbl 0751.05029
[36] A. O. Ivanov and A. A. Tuzhilin, Geometry of minimal networks and one-di-mensional Plateau problem. Uspekhi Mat. Nauk, 1992, vol. 47, no. 2 (284), Russian. · Zbl 0792.90083
[37] A. O. Ivanov and A. A. Tuzhilin, The Steiner problem for convex boundaries, 1: general case. Advances in Soviet Mathematics, 1993, vol. 15, pp. 15-92. · Zbl 0787.05056
[38] A. O. Ivanov and A. A. Tuzhilin, The Steiner problem for convex boundaries, 2: the regular case. Advances in Soviet Mathematics, 1993, vol. 15, pp. 93-131. · Zbl 0787.05057
[39] A. O. Ivanov and A. A. Tuzhilin, Minimal Networks. The Steiner Problem and Its Generalizations. N.W., Boca Raton, Florida, CRC Press, 1994. · Zbl 0842.90116
[40] A. O. Ivanov, I. Iskhakov, and A. A. Tuzhilin, Minimal networks spanning regularn-gons: linear tilings realization. Vestnik Moskov. Univ. Ser. Mat., 1993. English transl. in Moscow Univ. Math. Bull. · Zbl 0841.05020
[41] A. O. Ivanov, I. V. Ptitsina, and A. A. Tuzhilin, Classification of closed minimal networks on flat two-dimensional tori. Matem. Sbornik, 1992, vol. 183, no. 12, pp. 3-44 (Russian). · Zbl 0818.90125
[42] I. V. Shklyanko, The one dimensional Plateau problem on surfaces. Vestnik Moskov. Univ. Ser. Mat., 1989, no. 3, pp. 8-11 (Russian). English transl. in Moscow Univ. Math. Bull. (1989). · Zbl 0692.49027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.