Skip to main content
Springer Nature Link
Log in

Improving Upper and Lower Bounds for the Total Number of Edge Crossings of Euclidean Minimum Weight Laman Graphs

  • Conference paper
  • First Online:
Computing and Combinatorics (COCOON 2021)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 13025))

Included in the following conference series:

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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
eBook
USD 84.99
Price excludes VAT (USA)
Softcover Book
USD 109.99
Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    Throughout the paper, for two points p, q, we abuse the notation pq to denote the line segment between p and q or the length of itself, depending on the context.

  2. 2.

    Lemma 4.1 in [3] corresponds to Lemma 4(i)(ii).

  3. 3.

    Another terminology constrained geometric thickness of a graph is used in [4].

References

  1. Á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)

    Article  MathSciNet  Google Scholar 

  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). https://doi.org/10.1007/s00454-007-9026-x

    Article  MathSciNet  MATH  Google Scholar 

  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)

    Article  MathSciNet  Google Scholar 

  4. Bose, P., et al.: Some properties of \(k\)-Delaunay and \(k\)-Gabriel graphs. Comput. Geometry 46(2), 131–139 (2013)

    Article  MathSciNet  Google Scholar 

  5. Graver, J., Servatius, B., Servatius, H.: Combinatorial rigidity. graduate studies in mathematics, vol. 2. American Mathematical Society (1993)

    Google Scholar 

  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)

    Google Scholar 

  7. Lee, A., Streinu, I.: Pebble game algorithms and sparse graphs. Disc. Math. 308, 1425–1437 (2008)

    Article  MathSciNet  Google Scholar 

  8. Laman, G.: On graphs and rigidity of plane skeletal structures. J. Eng. Math. 4, 331–340 (1970)

    Article  MathSciNet  Google Scholar 

  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)

    Google Scholar 

  10. Thorpe, M.F., Duxbury, P.M. (eds.): Rigidity Theory and Applications. Kluwer Academic/Plenum Publishers, New York (1999)

    Google Scholar 

  11. Yao, A.C.: On constructing minimum spanning trees in \(k\)-dimensional space and related Problems. SIAM J. Comput. 11(4), 721–736 (1982)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Engineering, Osaka City University, Osaka, Japan

    Yuki Kobayashi

  2. Graduate School of Information Science, University of Hyogo, Kobe, Japan

    Yuya Higashikawa & Naoki Katoh

Authors
  1. Yuki Kobayashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Yuya Higashikawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Naoki Katoh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuki Kobayashi .

Editor information

Editors and Affiliations

  1. National Cheng Kung University, Tainan, Taiwan

    Chi-Yeh Chen

  2. National Tsing Hua University, Hsinchu, Taiwan

    Wing-Kai Hon

  3. National Taipei University of Business, Taoyuan, Taiwan

    Ling-Ju Hung

  4. National Taitung University, Taitung, Taiwan

    Chia-Wei Lee

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

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)

Publish with us

Policies and ethics

Search

Navigation