[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

On Embeddability of Unit Disk Graphs Onto Straight Lines

  • Published:
Theory of Computing Systems Aims and scope Submit manuscript

Abstract

Unit disk graphs are the intersection graphs of unit radius disks in the Euclidean plane. Deciding whether there exists an embedding of a given unit disk graph, i.e. unit disk graph recognition, is an important geometric problem, and has many application areas. In general, this problem is known to be \(\exists \mathbb {R}\)-complete. In some applications, the objects that correspond to unit disks, have predefined (geometrical) structures to be placed on. Hence, many researchers attacked this problem by restricting the domain of the disk centers. Following the same line, we also describe a polynomial-time reduction which shows that deciding whether a graph can be realized as unit disks onto given straight lines is NP-hard, when the given lines are parallel to either x-axis or y-axis. Adjusting the reduction, we also show that this problem is NP-complete when the given lines are only parallel to x-axis. We obtain those results using the idea of the logic engine introduced by Bhatt and Cosmadakis in 1987.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.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

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5

Similar content being viewed by others

Notes

  1. Note that this problem is different than embeddability of an edge weighted graph [27], since two disks must intersect if their centers are close enough.

  2. This problem is equivalent to the 2-coloring of 3-uniform hypergraphs. We choose to give the reduction from Monotone NAE3SAT as it is more intuitive to construct for our problem

References

  1. Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithm. 52(2), 134–151 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  2. Alomari, A., Aslam, N., varPhillips, W., Comeau, F.: Three-dimensional path planning model for mobile anchor-assisted localization in Wireless Sensor Networks. In: Proceedings of the 30th Canadian Conference on Electrical and Computer Engineering (CCECE), pp. 1–5 (2017)

  3. Aspnes, J., Eren, T., Goldenberg, D. K., Morse, A. S., Whiteley, W., Yang, Y. R., Anderson, B. D. O., Belhumeur, P. N.: A theory of network localization. IEEE Trans. Mob. Comput. 5(12), 1663–1678 (2006)

    Article  Google Scholar 

  4. Aspnes, J., Goldenberg, D., Yang, Y. R.: On the computational complexity of sensor network localization. In: Algorithmic Aspects of Wireless Sensor Networks, pp 32–44. Springer, Berlin (2004)

  5. Balasundaram, B., Butenko, S.: Optimization Problems in Unit-disk Graphs. Springer, Boston (2009)

    MATH  Google Scholar 

  6. Bhatt, S. N., Cosmadakis, S. S.: The complexity of minimizing wire lengths in VLSI layouts. Inf. Process. Lett. 25(4), 263–267 (1987)

    Article  MATH  Google Scholar 

  7. Bonnet, É., Giannopoulos, P., Kim, E. J., Rzȧżewski, P., Sikora, F.: QPTAS and subexponential algorithm for maximum clique on disk graphs. In: Proocedings of the 34th International Symposium on Computational Geometry (SoCG), vol. 99, pp. 12:1–12:15 (2018)

  8. Booth, K. S., Lueker, G. S.: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. J. Comput. Syst. Sci. 13(3), 335–379 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  9. Breu, H.: Algorithmic Aspects of Constrained Unit Disk Graphs. University of British Columbia, PhD thesis (1996)

    Google Scholar 

  10. Breu, H., Kirkpatrick, D. G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1), 3–24 (1998). Special Issue on Geometric Representations of Graphs

    Article  MathSciNet  MATH  Google Scholar 

  11. Çağırıcı, O.: Exploiting Coplanar Clusters to Enhance 3D Localization in Wireless Sensor Networks. Izmir University of Economics, Master’s thesis (2015)

    Google Scholar 

  12. Clark, B. N., Colbourn, C. J., Johnson, D. S.: Unit disk graphs. Discret. Math. 86(1), 165–177 (1991)

    MathSciNet  MATH  Google Scholar 

  13. da Fonseca, G. D., Pereira de, Sá, V. G., Machado, R. C. S., de Figueiredo, C. M. H.: On the recognition of unit disk graphs and the distance geometry problem with ranges. Discret. Appl. Math 197, 3–19 (2015). Distance Geometry and Applications

  14. Dil, B., Dulman, S., Havinga, P.: Range-Based Localization in Mobile Sensor Networks. In: Wireless Sensor Networks, pp 164–179. Springer, Berlin (2006)

  15. Evans, W., van Garderen, M., Löffler, M., Polishchuk, V.: Recognizing a DOG is hard, but not when it is thin and unit. In: Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), vol. 49, pp. 16:1–16:12 (2016)

  16. Fishburn, P. C.: Interval graphs and interval orders. Discret. Math. 55(2), 135–149 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  17. Fomin, F. V., Lokshtanov, D., Saurabh, S.: Bidimensionality and geometric graphs. In: Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SODA ’12, pp. 1563–1575. Society for Industrial and Applied Mathematics (2012)

  18. Gräf, A., Stumpf, M., Weißenfels, G.: On coloring unit disk graphs. Algorithmica 20, 277–293 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  19. Hayashi, T., Kawamura, A., Otachi, Y., Shinohara, H., Yamazaki, K.: Thin strip graphs. Discret. Appl. Math. 216, 203–210 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  20. Itai, A., Papadimitriou, C., Szwarcfiter, J.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676–686 (1982)

    Article  MathSciNet  MATH  Google Scholar 

  21. Ito, H., Kadoshita, M.: Tractability and intractability of problems on unit disk graphs parameterized by domain area. In: Proceedings of the 9th International Symposium on Operations Research and Its Applications (ISORA), pp. 120–127 (2010)

  22. Kang, R. J., Müller, T.: Sphere and dot product representations of graphs. Discret. Comput. Geom. 47, 548–568 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  23. Kuhn, F., Moscibroda, T., Wattenhofer, R.: Unit disk graph approximation. In: Proceedings of the 2004 Joint Workshop on Foundations of Mobile Computing (FOMC), DIALM-POMC ’04, pp. 17–23. Association for Computing Machinery (2004)

  24. Masuyama, S., Ibaraki, T., Hasegawa, T.: The computational complexity of the m-center problems on the plane. Trans. Inst. Electron. Commun. Eng. Jpn. Sect. E E64(2), 57–64 (1981)

    Google Scholar 

  25. McDiarmid, C., Müller, T.: Integer realizations of disk and segment graphs. J. Comb. Theory 103(1), 114–143 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  26. Neto, M. F., Goussevskaia, O., dos Santos, V. F.: Connectivity with backbone structures in obstructed wireless networks. Comput. Netw. 127(C), 266–281 (2017)

    Article  Google Scholar 

  27. Saxe, J.: Embeddability of weighted graphs in k-space is strongly NP-hard. CMU-CS-80-102. Carnegie-mellon University Department of Computer Science (1979)

  28. Schaefer, T. J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), STOC ’78, pp. 216–226 (1978)

Download references

Acknowledgements

I want to thank Petr Hliněný, Deniz Ağaoğlu Çağırıcı and Michał Dębski for their extensive comments and generous helps during the preparation of this manuscript.

Author information

Authors and Affiliations

  1. Department of Computer Science, Ryerson University, Toronto, Canada

    Onur Çağırıcı

Authors
  1. Onur Çağırıcı
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Onur Çağırıcı.

Additional information

Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

The author was affiliated with Masaryk University during the initial revision process and he was supported by the Czech Science Foundation, project no. 20-04567S. Now, the author is affiliated with the Ryerson University and he is supported by the Ryerson University Faculty of Science Dean’s Research Fund.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Çağırıcı, O. On Embeddability of Unit Disk Graphs Onto Straight Lines. Theory Comput Syst 67, 264–289 (2023). https://doi.org/10.1007/s00224-022-10110-y

Download citation

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00224-022-10110-y

Keywords

Search

Navigation