Improving upper and lower bounds for the total number of edge crossings of Euclidean minimum weight Laman graphs. (English) Zbl 07670467
Chen, Chi-Yeh (ed.) et al., Computing and combinatorics. 27th international conference, COCOON 2021, Tainan, Taiwan, October 24–26, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13025, 244-256 (2021).
Summary: 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.
For the entire collection see [Zbl 1507.68026].
For the entire collection see [Zbl 1507.68026].
MSC:
| 68Rxx | Discrete mathematics in relation to computer science |
References:
| [1] | Ábrego, BM; 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) · Zbl 1213.05179 · doi:10.1016/j.comgeo.2010.11.003 |
| [2] | 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) · Zbl 1147.52007 · doi:10.1007/s00454-007-9026-x |
| [3] | 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) · Zbl 1329.05076 · doi:10.1016/j.comgeo.2015.10.002 |
| [4] | Bose, P., Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs, Comput. Geometry, 46, 2, 131-139 (2013) · Zbl 1254.05042 · doi:10.1016/j.comgeo.2012.04.006 |
| [5] | Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. graduate studies in mathematics, vol. 2. American Mathematical Society (1993) · Zbl 0788.05001 |
| [6] | 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) |
| [7] | Lee, A.; Streinu, I., Pebble game algorithms and sparse graphs, Disc. Math., 308, 1425-1437 (2008) · Zbl 1136.05062 · doi:10.1016/j.disc.2007.07.104 |
| [8] | Laman, G., On graphs and rigidity of plane skeletal structures, J. Eng. Math., 4, 331-340 (1970) · Zbl 0213.51903 · doi:10.1007/BF01534980 |
| [9] | 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) |
| [10] | Thorpe, MF; Duxbury, PM, Rigidity Theory and Applications (1999), New York: Kluwer Academic/Plenum Publishers, New York |
| [11] | Yao, AC, On constructing minimum spanning trees in \(k\)-dimensional space and related Problems, SIAM J. Comput., 11, 4, 721-736 (1982) · Zbl 0492.68050 · doi:10.1137/0211059 |
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.
