Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points | SpringerLink
Skip to main content

Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points

  • Conference paper
LATIN 2012: Theoretical Informatics (LATIN 2012)

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

Included in the following conference series:

Abstract

Given a set P of n points in the plane, we solve the problems of constructing a geometric planar graph spanning P 1) of minimum degree 2, and 2) which is 2-edge connected, respectively, and has max edge length bounded by a factor of 2 times the optimal; we also show that the factor 2 is best possible given appropriate connectivity conditions on the set P, respectively. First, we construct in O(nlogn) time a geometric planar graph of minimum degree 2 and max edge length bounded by 2 times the optimal. This is then used to construct in O(nlogn) time a 2-edge connected geometric planar graph spanning P with max edge length bounded by \(\sqrt{5}\) times the optimal, assuming that the set P forms a connected Unit Disk Graph. Second, we prove that 2 times the optimal is always sufficient if the set of points forms a 2 edge connected Unit Disk Graph and give an algorithm that runs in O(n 2) time. We also show that for \(k \in O(\sqrt{n})\), there exists a set P of n points in the plane such that even though the Unit Disk Graph spanning P is k-vertex connected, there is no 2-edge connected geometric planar graph spanning P even if the length of its edges is allowed to be up to 17/16.

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

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /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
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Abellanas, M., García, A., Hurtado, F., Tejel, J., Urrutia, J.: Augmenting the connectivity of geometric graphs. Computational Geometry: Theory and Applications 40(3), 220–230 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  2. Al-Jubeh, M., Ishaque, M., Rédei, K., Souvaine, D.L., Tóth, C.D.: Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 902–912. Springer, Heidelberg (2009)

    Chapter  Google Scholar 

  3. Al-Jubeh, M., Ishaque, M., Rdei, K., Souvaine, D., Tth, C., Valtr, P.: Augmenting the edge connectivity of planar straight line graphs to three. Algorithmica 61, 971–999 (2011)

    Article  MathSciNet  MATH  Google Scholar 

  4. Cheriyan, J., Sebő, A., Szigeti, Z.: An Improved Approximation Algorithm for Minimum Size 2-Edge Connected Spanning Subgraphs. In: Bixby, R.E., Boyd, E.A., Ríos-Mercado, R.Z. (eds.) IPCO 1998. LNCS, vol. 1412, pp. 126–136. Springer, Heidelberg (1998)

    Chapter  Google Scholar 

  5. Dobrev, S., Kranakis, E., Krizanc, D., Morales Ponce, O., Stacho, L.: Approximating the edge length of 2-edge connected planar geometric graphs on a set of points. arXiv:1112.3523v1 (2012)

    Google Scholar 

  6. Gabriel, K.R., Sokal, R.R.: A new statistical approach to geographic variation analysis. Systematic Zoology 18(3), 259–278 (1969)

    Article  Google Scholar 

  7. García, A., Hurtado, F., Huemer, C., Tejel, J., Valtr, P.: On triconnected and cubic plane graphs on given point sets. Computational Geometry 42(9), 913–922 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  8. Jothi, R., Raghavachari, B., Varadarajan, S.: A 5/4-Approximation Algorithm for Minimum 2-Edge-Connectivity. In: The Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 725–734. Society for Industrial and Applied Mathematics, Philadelphia (2003)

    Google Scholar 

  9. Kranakis, E., Krizanc, D., Ponce, O.M., Stacho, L.: Bounded Length, 2-Edge Augmentation of Geometric Planar Graphs. In: Wu, W., Daescu, O. (eds.) COCOA 2010, Part I. LNCS, vol. 6508, pp. 385–397. Springer, Heidelberg (2010)

    Chapter  Google Scholar 

  10. Kranakis, E., Morales Ponce, O., Suomela, J.: Planar Subgraphs without Low-Degree Nodes. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 583–594. Springer, Heidelberg (2011)

    Chapter  Google Scholar 

  11. Parker, R.G., Rardin, R.L.: Guaranteed performance heuristics for the bottleneck traveling salesman problem. Oper. Res. Lett. 2(6), 269–272 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  12. Rutter, I., Wolff, A.: Augmenting the connectivity of planar and geometric graphs. Electronic Notes in Discrete Mathematics 31, 53–56 (2008)

    Article  MathSciNet  Google Scholar 

  13. Tóth, C.: Connectivity augmentation in plane straight line graphs. Electronic Notes in Discrete Mathematics 31, 49–52 (2008)

    Article  Google Scholar 

  14. Toussaint, T.: The relative neighbourhood graph of a finite planar set. Pattern Recognition 12(4), 261–268 (1980)

    Article  MathSciNet  MATH  Google Scholar 

  15. Urrutia, J.: Local solutions for global problems in wireless networks. J. of Discrete Algorithms 5, 395–407 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  16. Vempala, S., Vetta, A.: Factor 4/3 Approximations for Minimum 2-Connected Subgraphs. In: Jansen, K., Khuller, S. (eds.) APPROX 2000. LNCS, vol. 1913, pp. 262–273. Springer, Heidelberg (2000)

    Chapter  Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints and permissions

Copyright information

© 2012 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Dobrev, S., Kranakis, E., Krizanc, D., Morales-Ponce, O., Stacho, L. (2012). Approximating the Edge Length of 2-Edge Connected Planar Geometric Graphs on a Set of Points. In: Fernández-Baca, D. (eds) LATIN 2012: Theoretical Informatics. LATIN 2012. Lecture Notes in Computer Science, vol 7256. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-29344-3_22

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-29344-3_22

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-29343-6

  • Online ISBN: 978-3-642-29344-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics