nach oben

Theory of Computing Systems

Erschienen in:

17.12.2022

On Embeddability of Unit Disk Graphs Onto Straight Lines

verfasst von: Onur Çağırıcı

Erschienen in: Theory of Computing Systems | Ausgabe 2/2023

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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.

Vorheriger Artikel Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars

Nächster Artikel Correction to: Submodular Functions and Rooted Trees

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

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.

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

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)MathSciNetCrossRefMATH

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)

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)CrossRef

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)

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

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

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)

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)MathSciNetCrossRefMATH

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

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 GraphsMathSciNetCrossRefMATH

11.

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

12.

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

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)MathSciNetCrossRefMATH

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)MathSciNetCrossRefMATH

19.

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

20.

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

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)MathSciNetCrossRefMATH

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)

25.

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

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)CrossRef

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)

Titel: On Embeddability of Unit Disk Graphs Onto Straight Lines
verfasst von: Onur Çağırıcı
Publikationsdatum: 17.12.2022
Verlag: Springer US
Erschienen in: Theory of Computing Systems / Ausgabe 2/2023
Print ISSN: 1432-4350
Elektronische ISSN: 1433-0490
DOI: https://doi.org/10.1007/s00224-022-10110-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2023

Polynomially Ambiguous Unary Weighted Automata over Fields

Local Deal-Agreement Algorithms for Load Balancing in Dynamic General Graphs

Correction to: On the Transformation of LL(k)-linear to LL(1)-linear Grammars

Preface of the Special Issue Dedicated to Selected Papers from CSR 2020

Complexity Limitations on One-turn Quantum Refereed Games

On the Transformation of LL(k)-linear to LL(1)-linear Grammars

Premium Partner