There are plane spanners of degree 4 and moderate stretch factor. (English) Zbl 1314.05132
Summary: Let \(\mathcal E\) be the complete Euclidean graph on a set of points embedded in the plane. Given a constant \(t \geq 1\), a spanning subgraph \(G\) of \(\mathcal E\) is said to be a \(t\)-spanner, or simply a spanner, if for any pair of nodes \(u,v\) in \(\mathcal E\) the distance between \(u\) and \(v\) in \(G\) is at most \(t\) times their distance in \(\mathcal E\). The constant \(t\) is referred to as the stretch factor. A spanner is plane if its edges do not cross.
This paper considers the question: “What is the smallest maximum degree that can always be achieved for a plane spanner of \(\mathcal E\)?” Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper, we show that the complete Euclidean graph always contains a plane spanner of maximum degree 4 and make a big step toward closing the question. The stretch factor of the spanner is bounded by 156.82. Our construction leads to an efficient algorithm for obtaining the spanner from Chew’s \(L_1\)-Delaunay triangulation.
This paper considers the question: “What is the smallest maximum degree that can always be achieved for a plane spanner of \(\mathcal E\)?” Without the planarity constraint, it is known that the answer is 3 which is thus the best known lower bound on the degree of any plane spanner. With the planarity requirement, the best known upper bound on the maximum degree is 6, the last in a long sequence of results improving the upper bound. In this paper, we show that the complete Euclidean graph always contains a plane spanner of maximum degree 4 and make a big step toward closing the question. The stretch factor of the spanner is bounded by 156.82. Our construction leads to an efficient algorithm for obtaining the spanner from Chew’s \(L_1\)-Delaunay triangulation.
MSC:
| 05C60 | Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) |
| 05C10 | Planar graphs; geometric and topological aspects of graph theory |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Bonichon, N., Gavoille, C., Hanusse, N., Perković, L.: Plane spanners of maximum degree six. In: Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 6198, pp. 19-30. Springer, Berlin (2010) · Zbl 1287.68168 |
| [2] | Bonichon, N., Gavoille, C., Hanusse, N., Perković, L.: The stretch factor of \[{L}_1\] L1- and \[{L}_\infty\] L∞-Delaunay triangulations. In: Proceedings of the 20th Annual European Symposium on Algorithms (ESA). Lecture Notes in Computer Science, vol. 7501, pp. 205-216. Springer, Berlin (2012) · Zbl 1365.68437 |
| [3] | Bose, P., Smid, M.: On plane geometric spanners: a survey and open problems. Comput. Geom. 46(7), 818-830 (2013) · Zbl 1270.05032 · doi:10.1016/j.comgeo.2013.04.002 |
| [4] | Bose, P., Morin, P., Stojmenović, I., Urrutia, J.: Routing with guaranteed delivery in ad hoc wireless networks. Wirel. Netw. 7(6), 609-616 (2001) · Zbl 0996.68012 · doi:10.1023/A:1012319418150 |
| [5] | Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42(3-4), 249-264 (2005) · Zbl 1086.68136 · doi:10.1007/s00453-005-1168-8 |
| [6] | Bose, P., Smid, M., Xu, D.: Delaunay and diamond triangulations contain spanners of bounded degree. Int. J. Comput. Geom. Appl. 19(2), 119-140 (2009) · Zbl 1167.65335 · doi:10.1142/S0218195909002861 |
| [7] | Bose, P., Carmi, P., Chaitman-Yerushalmi, L.: On bounded degree plane strong geometric spanners. J. Discrete Algorithms 15, 16-31 (2012) · Zbl 1247.68306 · doi:10.1016/j.jda.2012.03.004 |
| [8] | Bose, P., Damian, M., Douïeb, K., O’Rourke, J., Seamone, B., Smid, M.H.M., Wuhrer, \[S.: \pi /2\] π/2-Angle Yao graphs are spanners. Int. J. Comput. Geom. Appl. 22(1), 61-82 (2012) · Zbl 1251.05036 · doi:10.1142/S0218195912600047 |
| [9] | Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: Competitive routing on a bounded-degree plane spanner. In: Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG), pp. 299-304 (2012) · Zbl 1297.68232 |
| [10] | Bose, P., Fagerberg, R., van Renssen, A., Verdonschot, S.: On plane constrained bounded-degree spanners. In: Proceedings of the 10th Latin American Symposium on Theoretical Informatics (LATIN). Lecture Notes in Computer Science, vol. 7256, pp. 85-96 (2012) · Zbl 1297.68232 |
| [11] | Chew, L.P.: There is a planar graph almost as good as the complete graph. In: Proceedings of the Second Annual Symposium on Computational Geometry (SoCG), pp. 169-177 (1986) · Zbl 1167.65335 |
| [12] | Chew, L.P.: There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci. 39(2), 205-219 (1989) · Zbl 0682.05032 · doi:10.1016/0022-0000(89)90044-5 |
| [13] | Das, G., Heffernan, P.: Constructing degree-3 spanners with other sparseness properties. Int. J. Found. Comput. Sci. 7(2), 121-136 (1996) · Zbl 0852.68100 · doi:10.1142/S0129054196000105 |
| [14] | Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. In: Proceedings of the 28th Annual Symposium on Foundations of Computer Science (FOCS), pp. 20-26. IEEE Computer Society, Silver Spring, MD (1987) · Zbl 0693.05045 |
| [15] | Kanj, I., Perković, L.: On geometric spanners of Euclidean and unit disk graphs. In. In Proceedings of the 25th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. hal-00231084, pp. 409-420. HAL (2008) · Zbl 1259.68163 |
| [16] | Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete Comput. Geom. 7(1), 13-28 (1992) · Zbl 0751.52004 · doi:10.1007/BF02187821 |
| [17] | Li, X.Y., Wang, Y.: Efficient construction of low weight bounded degree planar spanner. Int. J. Comput. Geom. Appl. 14(1-2), 69-84 (2004) · Zbl 1093.68130 · doi:10.1142/S0218195904001366 |
| [18] | Salowe, J.: Euclidean spanner graphs with degree four. Discrete Appl. Math. 54(1), 55-66 (1994) · Zbl 0812.68104 · doi:10.1016/0166-218X(94)90133-3 |
| [19] | Wang, Y., Li, X.Y.: Localized construction of bounded degree and planar spanner for wireless ad hoc networks. Mob. Netw. Appl. 11(2), 161-175 (2006) · doi:10.1007/s11036-006-4469-5 |
| [20] | Xia, G.: The stretch factor of the Delaunay triangulation is less than 1.998. SIAM J. Comput. 42(4), 1620-1659 (2013) · Zbl 1302.65059 · doi:10.1137/110832458 |
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.
