{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:55Z","timestamp":1740109375962,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T00:00:00Z","timestamp":1671235200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001824","name":"Grantov\u00e1 Agentura \u010cesk\u00e9 Republiky","doi-asserted-by":"publisher","award":["20-04567S"],"award-info":[{"award-number":["20-04567S"]}],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007891","name":"Ryerson University","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100007891","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2023,4]]},"DOI":"10.1007\/s00224-022-10110-y","type":"journal-article","created":{"date-parts":[[2022,12,17]],"date-time":"2022-12-17T14:03:06Z","timestamp":1671285786000},"page":"264-289","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["On Embeddability of Unit Disk Graphs Onto Straight Lines"],"prefix":"10.1007","volume":"67","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4785-7496","authenticated-orcid":false,"given":"Onur","family":"\u00c7a\u011f\u0131r\u0131c\u0131","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,12,17]]},"reference":[{"issue":"2","key":"10110_CR1","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J Alber","year":"2004","unstructured":"Alber, J., Fiala, J.: Geometric separation and exact solutions for the parameterized independent set problem on disk graphs. J. Algorithm. 52(2), 134\u2013151 (2004)","journal-title":"J. Algorithm."},{"key":"10110_CR2","doi-asserted-by":"crossref","unstructured":"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\u20135 (2017)","DOI":"10.1109\/CCECE.2017.7946681"},{"issue":"12","key":"10110_CR3","doi-asserted-by":"publisher","first-page":"1663","DOI":"10.1109\/TMC.2006.174","volume":"5","author":"J Aspnes","year":"2006","unstructured":"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\u20131678 (2006)","journal-title":"IEEE Trans. Mob. Comput."},{"key":"10110_CR4","doi-asserted-by":"crossref","unstructured":"Aspnes, J., Goldenberg, D., Yang, Y. R.: On the computational complexity of sensor network localization. In: Algorithmic Aspects of Wireless Sensor Networks, pp 32\u201344. Springer, Berlin (2004)","DOI":"10.1007\/978-3-540-27820-7_5"},{"key":"10110_CR5","volume-title":"Optimization Problems in Unit-disk Graphs","author":"B Balasundaram","year":"2009","unstructured":"Balasundaram, B., Butenko, S.: Optimization Problems in Unit-disk Graphs. Springer, Boston (2009)"},{"issue":"4","key":"10110_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1016\/0020-0190(87)90173-6","volume":"25","author":"SN Bhatt","year":"1987","unstructured":"Bhatt, S. N., Cosmadakis, S. S.: The complexity of minimizing wire lengths in VLSI layouts. Inf. Process. Lett. 25(4), 263\u2013267 (1987)","journal-title":"Inf. Process. Lett."},{"key":"10110_CR7","unstructured":"Bonnet, \u00c9., Giannopoulos, P., Kim, E. J., Rza\u0307\u017cewski, 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\u201312:15 (2018)"},{"issue":"3","key":"10110_CR8","doi-asserted-by":"publisher","first-page":"335","DOI":"10.1016\/S0022-0000(76)80045-1","volume":"13","author":"KS Booth","year":"1976","unstructured":"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\u2013379 (1976)","journal-title":"J. Comput. Syst. Sci."},{"key":"10110_CR9","volume-title":"Algorithmic Aspects of Constrained Unit Disk Graphs","author":"H Breu","year":"1996","unstructured":"Breu, H.: Algorithmic Aspects of Constrained Unit Disk Graphs. University of British Columbia, PhD thesis (1996)"},{"issue":"1","key":"10110_CR10","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/S0925-7721(97)00014-X","volume":"9","author":"H Breu","year":"1998","unstructured":"Breu, H., Kirkpatrick, D. G.: Unit disk graph recognition is NP-hard. Comput. Geom. 9(1), 3\u201324 (1998). Special Issue on Geometric Representations of Graphs","journal-title":"Comput. Geom."},{"key":"10110_CR11","volume-title":"Exploiting Coplanar Clusters to Enhance 3D Localization in Wireless Sensor Networks","author":"O \u00c7a\u011f\u0131r\u0131c\u0131","year":"2015","unstructured":"\u00c7a\u011f\u0131r\u0131c\u0131, O.: Exploiting Coplanar Clusters to Enhance 3D Localization in Wireless Sensor Networks. Izmir University of Economics, Master\u2019s thesis (2015)"},{"issue":"1","key":"10110_CR12","first-page":"165","volume":"86","author":"BN Clark","year":"1991","unstructured":"Clark, B. N., Colbourn, C. J., Johnson, D. S.: Unit disk graphs. Discret. Math. 86(1), 165\u2013177 (1991)","journal-title":"Discret. Math."},{"key":"10110_CR13","doi-asserted-by":"crossref","unstructured":"da Fonseca, G. D., Pereira de, S\u00e1, 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\u201319 (2015). Distance Geometry and Applications","DOI":"10.1016\/j.dam.2014.08.014"},{"key":"10110_CR14","doi-asserted-by":"crossref","unstructured":"Dil, B., Dulman, S., Havinga, P.: Range-Based Localization in Mobile Sensor Networks. In: Wireless Sensor Networks, pp 164\u2013179. Springer, Berlin (2006)","DOI":"10.1007\/11669463_14"},{"key":"10110_CR15","unstructured":"Evans, W., van Garderen, M., L\u00f6ffler, 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\u201316:12 (2016)"},{"issue":"2","key":"10110_CR16","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(85)90042-1","volume":"55","author":"PC Fishburn","year":"1985","unstructured":"Fishburn, P. C.: Interval graphs and interval orders. Discret. Math. 55(2), 135\u2013149 (1985)","journal-title":"Discret. Math."},{"key":"10110_CR17","doi-asserted-by":"crossref","unstructured":"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 \u201912, pp. 1563\u20131575. Society for Industrial and Applied Mathematics (2012)","DOI":"10.1137\/1.9781611973099.124"},{"key":"10110_CR18","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/PL00009196","volume":"20","author":"A Gr\u00e4f","year":"1998","unstructured":"Gr\u00e4f, A., Stumpf, M., Wei\u00dfenfels, G.: On coloring unit disk graphs. Algorithmica 20, 277\u2013293 (1998)","journal-title":"Algorithmica"},{"key":"10110_CR19","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1016\/j.dam.2015.01.018","volume":"216","author":"T Hayashi","year":"2017","unstructured":"Hayashi, T., Kawamura, A., Otachi, Y., Shinohara, H., Yamazaki, K.: Thin strip graphs. Discret. Appl. Math. 216, 203\u2013210 (2017)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"10110_CR20","doi-asserted-by":"publisher","first-page":"676","DOI":"10.1137\/0211056","volume":"11","author":"A Itai","year":"1982","unstructured":"Itai, A., Papadimitriou, C., Szwarcfiter, J.: Hamilton paths in grid graphs. SIAM J. Comput. 11(4), 676\u2013686 (1982)","journal-title":"SIAM J. Comput."},{"key":"10110_CR21","unstructured":"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\u2013127 (2010)"},{"key":"10110_CR22","doi-asserted-by":"publisher","first-page":"548","DOI":"10.1007\/s00454-012-9394-8","volume":"47","author":"RJ Kang","year":"2012","unstructured":"Kang, R. J., M\u00fcller, T.: Sphere and dot product representations of graphs. Discret. Comput. Geom. 47, 548\u2013568 (2012)","journal-title":"Discret. Comput. Geom."},{"key":"10110_CR23","doi-asserted-by":"crossref","unstructured":"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 \u201904, pp. 17\u201323. Association for Computing Machinery (2004)","DOI":"10.1145\/1022630.1022634"},{"issue":"2","key":"10110_CR24","first-page":"57","volume":"E64","author":"S Masuyama","year":"1981","unstructured":"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\u201364 (1981)","journal-title":"Trans. Inst. Electron. Commun. Eng. Jpn. Sect. E"},{"issue":"1","key":"10110_CR25","doi-asserted-by":"publisher","first-page":"114","DOI":"10.1016\/j.jctb.2012.09.004","volume":"103","author":"C McDiarmid","year":"2013","unstructured":"McDiarmid, C., M\u00fcller, T.: Integer realizations of disk and segment graphs. J. Comb. Theory 103(1), 114\u2013143 (2013)","journal-title":"J. Comb. Theory"},{"issue":"C","key":"10110_CR26","doi-asserted-by":"publisher","first-page":"266","DOI":"10.1016\/j.comnet.2017.08.023","volume":"127","author":"MF Neto","year":"2017","unstructured":"Neto, M. F., Goussevskaia, O., dos Santos, V. F.: Connectivity with backbone structures in obstructed wireless networks. Comput. Netw. 127(C), 266\u2013281 (2017)","journal-title":"Comput. Netw."},{"key":"10110_CR27","unstructured":"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)"},{"key":"10110_CR28","doi-asserted-by":"crossref","unstructured":"Schaefer, T. J.: The complexity of satisfiability problems. In: Proceedings of the 10th Annual ACM Symposium on Theory of Computing (STOC), STOC \u201978, pp. 216\u2013226 (1978)","DOI":"10.1145\/800133.804350"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-022-10110-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-022-10110-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,14]],"date-time":"2023-03-14T10:08:25Z","timestamp":1678788505000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-022-10110-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,12,17]]},"references-count":28,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["10110"],"URL":"https:\/\/doi.org\/10.1007\/s00224-022-10110-y","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2022,12,17]]},"assertion":[{"value":"9 November 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 December 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}