Abstract
Given a triangulation G, whose vertex set V is a set of n points in the plane, and given a real number γ with 0<γ<π, we design an O(n)-time algorithm that constructs a connected spanning subgraph G′ of G whose maximum degree is at most 14+⌈2π/γ⌉. If G is the Delaunay triangulation of V, and γ= 2π/3, we show that G′ is a t-spanner of V (for some constant t) with maximum degree at most 17, thereby improving the previously best known degree bound of 23. If G is the graph consisting of all Delaunay edges of length at most 1, and γ= π/3, we show that G′ is a t-spanner (for some constant t) of the unit-disk graph of V, whose maximum degree is at most 20, thereby improving the previously best known degree bound of 25. Finally, if G is a triangulation satisfying the diamond property, then for a specific range of values of γ dependent on the angle of the diamonds, we show that G′ is a t-spanner of V (for some constant t) whose maximum degree is bounded by a constant dependent on γ.
This research was supported by the Natural Science and Engineering Research Council of Canada.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bose, P., Gudmundsson, J., Smid, M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249–264 (2005)
Bose, P., Maheshwari, A., Narasimhan, G., Smid, M., Zeh, N.: Approximating geometric bottleneck shortest paths. Computational Geometry: Theory and Applications 29, 233–249 (2004)
Bose, P., Morin, P.: Online routing in triangulations. SIAM Journal on Computing 33, 937–951 (2004)
Bose, P., Smid, M., Xu, D.: Diamond triangulations contain spanners of bounded degree. Carleton University, Computer Science Technical Report (2006)
Chew, L.P.: There are planar graphs almost as good as the complete graph. Journal of Computer and System Sciences 39, 205–219 (1989)
Das, G., Joseph, D.: Which triangulations approximate the complete graph? In: Djidjev, H.N. (ed.) Optimal Algorithms. LNCS, vol. 401, pp. 168–192. Springer, Heidelberg (1989)
Dobkin, D.P., Friedman, S.J., Supowit, K.J.: Delaunay graphs are almost as good as complete graphs. Discrete & Computational Geometry 5, 399–407 (1990)
Keil, J.M., Gutwin, C.A.: Classes of graphs which approximate the complete Euclidean graph. Discrete & Computational Geometry 7, 13–28 (1992)
Lee, A.W.: Diamonds are a plane graph’s best friend. Master’s thesis, School of Computer Science, Carleton University, Ottawa (2004)
Li, X.-Y., Wang, Y.: Efficient construction of low weighted bounded degree planar spanner. International Journal of Computational Geometry & Applications 14, 69–84 (2004)
Narasimhan, G., Smid, M.: Geometric Spanner Networks. Cambridge University Press, Cambridge (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bose, P., Smid, M., Xu, D. (2006). Diamond Triangulations Contain Spanners of Bounded Degree. In: Asano, T. (eds) Algorithms and Computation. ISAAC 2006. Lecture Notes in Computer Science, vol 4288. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11940128_19
Download citation
DOI: https://doi.org/10.1007/11940128_19
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-49694-6
Online ISBN: 978-3-540-49696-0
eBook Packages: Computer ScienceComputer Science (R0)