Abstract
We investigate the total number of edge crossings (i.e., the crossing number) of the Euclidean minimum weight Laman graph \(\mathsf {MLG}(P)\) on a planar point set P. Bereg et al. (2016) showed that the upper and lower bounds for the crossing number of \(\mathsf {MLG}(P)\) are \(6|P|-9\) and \(|P|-3\), respectively. In this paper, we improve these upper and lower bounds given by Bereg et al. (2016) to \(2.5|P|-5\) and \((1.25-\varepsilon )|P|\) for any \(\varepsilon > 0\), respectively. Especially, for improving the upper bound, we introduce a novel counting scheme based on some geometric observations.
This work is supported by JST CREST Grant Number JPMJCR1402.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Ábrego, B.M., Fabila-Monroy, R., Fernández-Merchant, S., Flores-Peñaloza, D., Hurtado, F., Sacristán, V., Saumell, M.: On crossing numbers of geometric proximity graphs. Comput. Geometry 44(4), 216–233 (2011)
Avis, D., Katoh, N., Ohsaki, M., Streinu, I., Tanigawa, S.: Enumerating constrained non-crossing minimally rigid frameworks. Disc. Comput. Geometry 40(1), 31–46 (2007). https://doi.org/10.1007/s00454-007-9026-x
Bereg, S., Hong, S.-H., Katoh, N., Poon, S.-H., Tanigawa, S.: On the edge crossing properties of Euclidean minimum weight Laman graphs. Comput. Geometry Theory Appl. 51, 15–24 (2016)
Bose, P., et al.: Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs. Comput. Geometry 46(2), 131–139 (2013)
Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. graduate studies in mathematics, vol. 2. American Mathematical Society (1993)
Grötzsch, H.: Zur Theorie der diskreten Gebilde. VII. Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel. Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe, vol. 8, pp. 109–120 (1959)
Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Disc. Math. 308, 1425–1437 (2008)
Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331–340 (1970)
Servatius, B.: The geometry of frameworks: Rigidity, mechanisms and cad. In: Gorini, C.A. (Ed.), Geometry at Work: A Collection of Papers Showing Applications of Geometry. Cambridge University Press (2000)
Thorpe, M.F., Duxbury, P.M. (eds.): Rigidity Theory and Applications. Kluwer Academic/Plenum Publishers, New York (1999)
Yao, A.C.: On constructing minimum spanning trees in \(k\)-dimensional space and related Problems. SIAM J. Comput. 11(4), 721–736 (1982)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Kobayashi, Y., Higashikawa, Y., Katoh, N. (2021). Improving Upper and Lower Bounds for the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs. In: Chen, CY., Hon, WK., Hung, LJ., Lee, CW. (eds) Computing and Combinatorics. COCOON 2021. Lecture Notes in Computer Science(), vol 13025. Springer, Cham. https://doi.org/10.1007/978-3-030-89543-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-030-89543-3_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-89542-6
Online ISBN: 978-3-030-89543-3
eBook Packages: Computer ScienceComputer Science (R0)