Advanced search
Publication Cover
International Journal of Computer Mathematics: Computer Systems Theory Volume 8, 2023 - Issue 1: Special Issue on 27th International Computing and Combinatorics Conference (Selected Papers from COCOON 2021) - Part II; Guest Editors: Wing-Kai Hon, Ling-Ju Hung, and Chia-Wei Lee
Submit an article Journal homepage
36
Views
0
CrossRef citations to date
0
Altmetric
27th International Computing and Combinatorics Conference (Selected Papers from COCOON 2021)

Efficient algorithms and edge crossing properties of Euclidean minimum weight Laman graphs

Yuya Higashikawaa Graduate School of Information Science, University of Hyogo, Kobe, Japan
,
Naoki Katoha Graduate School of Information Science, University of Hyogo, Kobe, Japan
&
Yuki Kobayashib Department of Engineering, Osaka Metropolitan University, Osaka, JapanCorrespondence[email protected]
Pages 67-79 | Received 18 Feb 2022, Accepted 09 Feb 2023, Published online: 19 Mar 2023

References

  • B.M. Ábrego, R. Fabila-Monroy, S. Fernández-Merchant, D. Flores-Peñaloza, F. Hurtado, V. Sacristán, and M. Saumell, On crossing numbers of geometric proximity graphs, Comput. Geom. 44 (2011), pp. 216–233. https://doi.org/10.1016/j.comgeo.2010.11.003
  • S. Bereg, S. -H. Hong, N. Katoh, S. -H. Poon, and S. Tanigawa, On the edge crossing properties of Euclidean minimum weight Laman graphs, Comput. Geom. Theory Appl. 51 (2016), pp. 15–24. https://doi.org/10.1016/j.comgeo.2015.10.002
  • P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristán, and M. Saumell, Some properties of k-Delaunay and k-Gabriel graphs, Comput. Geom. 46 (2013), pp. 131–139. https://doi.org/10.1016/j.comgeo.2012.04.006
  • J. Graver, B. Servatius, and H. Servatius, Combinatorial Rigidity, Graduate Studies in Mathematics, vol. 2, American Mathematical Society, 1993.
  • H. Grötzsch, 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 8 (1959), pp. 109–120.
  • J. Kleinberg and É. Tardos, Algorithm Design, Pearson Education India, 2006.
  • Y. Koabayashi, Y. Higashikawa, and N. Katoh, Improving upper and lower bounds for the total number of edge crossings of euclidean minimum weight Laman graphs, in International Computing and Combinatorics Conference, 2021, pp. 244–256. https://doi.org/10.1007/978-3-030-89543-3_21
  • A. Lee and I. Streinu, Pebble game algorithms and sparse graphs, Discrete Math. 308 (2008), pp. 1425–1437. https://doi.org/10.1016/j.disc.2007.07.104
  • J.G. Oxley, Matroid Theory, Oxford University Press, USA, 2006.
  • G. Laman, On graphs and rigidity of plane skeletal structures, J. Eng. Math. 4 (1970), pp. 331–340. https://doi.org/10.1007/BF01534980
  • B. Servatius, The geometry of frameworks: Rigidity, mechanisms and cad, in Geometry at Work: A Collection of Papers Showing Applications of Geometry, C.A. Gorini, Ed., Cambridge University Press, 2000.
  • T.H. Su and R.C. Chang, The k-Gabriel graphs and their applications. in International Symposium on Algorithms, 1990, pp. 66–75.https://doi.org/10.1007/3-540-52921-7_56
  • M.F. Thorpe and P.M. Duxbury, (eds.), Rigidity Theory and Applications, Kluwer Academic/Plenum Publishers, New York, 1999. https://doi.org/10.1007/b115749
  • A.C. Yao, On constructing minimum spanning trees in k-dimensional space and related problems, SIAM J. Comput. 11 (1982), pp. 721–736. https://doi.org/10.1137/0211059

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.