Document Open Access Logo

Recognizing a DOG is Hard, But Not When It is Thin and Unit

Authors William Evans, Mereke van Garderen, Maarten Löffler, Valentin Polishchuk

PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.16.pdf
  • Filesize: 0.56 MB
  • 12 pages

Document Identifiers

Author Details

William Evans
Mereke van Garderen
Maarten Löffler
Valentin Polishchuk

Cite As Get BibTex

William Evans, Mereke van Garderen, Maarten Löffler, and Valentin Polishchuk. Recognizing a DOG is Hard, But Not When It is Thin and Unit. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 16:1-16:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FUN.2016.16

Abstract

We define the notion of disk-obedience for a set of disks in the plane and give results for diskobedient graphs (DOGs), which are disk intersection graphs (DIGs) that admit a planar embedding with vertices inside the corresponding disks. We show that in general it is hard to recognize a DOG, but when the DIG is thin and unit (i.e., when the disks are unit disks), it can be done in linear time.

Subject Classification

Keywords
  • graph drawing
  • planar graphs
  • disk intersection graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Patrizio Angelini, Giordano Da Lozzo, Marco Di Bartolomeo, Giuseppe Di Battista, Seok-Hee Hong, Maurizio Patrignani, and Vincenzo Roselli. Anchored drawings of planar graphs. In Graph Drawing, volume 8871 of Lecture Notes in Computer Science, pages 404-415. Springer, 2014. Google Scholar
  2. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, and Fabrizio Frati. Strip planarity testing. In Stephen K. Wismath and Alexander Wolff, editors, Graph Drawing, volume 8242 of Lecture Notes in Computer Science, pages 37-48. Springer, 2013. Google Scholar
  3. Esther M Arkin, Michael A Bender, Erik D Demaine, Sándor P Fekete, Joseph SB Mitchell, and Saurabh Sethia. Optimal covering tours with turn costs. SIAM Journal on Computing, 35(3):531-566, 2005. Google Scholar
  4. Esther M Arkin, Sándor P Fekete, Kamrul Islam, Henk Meijer, Joseph SB Mitchell, Yurai Núñez-Rodríguez, Valentin Polishchuk, David Rappaport, and Henry Xiao. Not being (super) thin or solid is hard: A study of grid Hamiltonicity. Computational Geometry, 42(6):582-605, 2009. Google Scholar
  5. Lali Barrière, Pierre Fraigniaud, Lata Narayanan, and Jaroslav Opatrny. Robust position-based routing in wireless ad hoc networks with irregular transmission ranges. WCMC, 3(2):141-153, 2003. URL: http://dx.doi.org/10.1002/wcm.108.
  6. Prosenjit Bose, Pat Morin, Ivan Stojmenović, and Jorge Urrutia. Routing with guaranteed delivery in ad hoc wireless networks. Wireless networks, 7(6):609-616, 2001. Google Scholar
  7. Kevin Buchin, Irina Kostitsyna, Maarten Löffler, and Rodrigo I Silveira. Region-based approximation algorithms for visibility between imprecise locations. In ALENEX, pages 94-103. SIAM, 2015. Google Scholar
  8. Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer. Preprocessing imprecise points for Delaunay triangulation: Simplified and extended. Algorithmica, 61(3):674-693, 2011. URL: http://dx.doi.org/10.1007/s00453-010-9430-0.
  9. Hubie Chen. A rendezvous of logic, complexity, and algebra. ACM Comput. Surv., 42(1):2:1-2:32, December 2009. URL: http://dx.doi.org/10.1145/1592451.1592453.
  10. M.B. Cozzens. Higher and Multi-dimensional Analogues of Interval Graphs. PhD thesis, Rutgers University, 1981. Google Scholar
  11. Hongwei Du, Xiaohua Jia, Deying Li, and Weili Wu. Coloring of double disk graphs. J. Global Opt, 28(1):115-119, 2004. URL: http://dx.doi.org/10.1023/B:JOGO.0000006750.85332.0f.
  12. Alon Efrat, Sándor P Fekete, Joseph SB Mitchell, Valentin Polishchuk, and Jukka Suomela. Improved approximation algorithms for relay placement. ACM Transactions on Algorithms, 12(2):20, 2015. Google Scholar
  13. M. Gromov. Hyperbolic groups. In S. M. Gersten, editor, Essays in Group Theory, pages 75-263. Springer New York, 1987. Google Scholar
  14. Marja Hassinen, Joel Kaasinen, Evangelos Kranakis, Valentin Polishchuk, Jukka Suomela, and Andreas Wiese. Analysing local algorithms in location-aware quasi-unit-disk graphs. Discr Appl Math, 159(15):1566-1580, 2011. URL: http://dx.doi.org/10.1016/j.dam.2011.05.004.
  15. Jean-Claude Hausmann. On the Vietoris-Rips complexes and a cohomology theory for metric spaces. In F. Quinn, editor, Annals of Mathematics Studies, volume 138, pages 175-188, Princeton, N.J., 1995. Princeton University Press. Prospects in topology : proceedings of a conference in honor of William Browder. Google Scholar
  16. Hiroshi Imai and Takao Asano. Finding the connected components and a maximum clique of an intersection graph of rectangles in the plane. Journal of Algorithms, 4(4):310-323, 1983. URL: http://dx.doi.org/http://dx.doi.org/10.1016/0196-6774(83)90012-3.
  17. Balázs Keszegh, János Pach, and Domotor Palvolgyi. Drawing planar graphs of bounded degree with few slopes. SIAM Journal on Discrete Mathematics, 27(2):1171-1183, 2013. Google Scholar
  18. Alexander Kröller, Sándor P Fekete, Dennis Pfisterer, and Stefan Fischer. Deterministic boundary recognition and topology extraction for large sensor networks. In SoDA, pages 1000-1009, 2006. Google Scholar
  19. Sven O Krumke, Madhav V Marathe, and SS Ravi. Models and approximation algorithms for channel assignment in radio networks. Wireless networks, 7(6):575-584, 2001. Google Scholar
  20. Fabian Kuhn, Thomas Moscibroda, and Rogert Wattenhofer. Unit disk graph approximation. In Proceedings of the 2004 joint workshop on Foundations of mobile computing, pages 17-23. ACM, 2004. Google Scholar
  21. Fabian Kuhn, Roger Wattenhofer, and Aaron Zollinger. Ad hoc networks beyond unit disk graphs. Wireless Networks, 14(5):715-729, 2007. URL: http://dx.doi.org/10.1007/s11276-007-0045-6.
  22. Fabian Kuhn, Rogert Wattenhofer, Yan Zhang, and Aaron Zollinger. Geometric ad-hoc routing: of theory and practice. In PoDC, pages 63-72, 2003. Google Scholar
  23. David Lichtenstein. Planar formulae and their uses. SIAM J. Comput., 11(2):329-343, 1982. URL: http://dx.doi.org/10.1137/0211025.
  24. Maarten Löffler. Existence and computation of tours through imprecise points. IJCGA, 21(1):1-24, 2011. URL: http://dx.doi.org/10.1142/S0218195911003524.
  25. Maarten Löffler and Wolfgang Mulzer. Unions of onions: Preprocessing imprecise points for fast onion decomposition. JoCG, 5(1):1-13, 2014. URL: http://jocg.org/index.php/jocg/article/view/140.
  26. Maarten Löffler and Marc van Kreveld. Largest and smallest convex hulls for imprecise points. Algorithmica, 56(2):235-269, 2010. Google Scholar
  27. John Nolan. Bisectored unit disk graphs. Networks, 43(3):141-152, 2004. URL: http://dx.doi.org/10.1002/net.10111.
  28. Maurizio Patrignani. On extending a partial straight-line drawing. Int. J. Found. CS, 17(5):1061-1070, 2006. URL: http://dx.doi.org/10.1142/S0129054106004261.
  29. Thomas J. Schaefer. The complexity of satisfiability problems. In SToC'78, STOC'78, pages 216-226. ACM, 1978. URL: http://dx.doi.org/10.1145/800133.804350.
  30. L. Vietoris. Über den höheren zusammenhang kompakter räume und eine klasse von zusammenhangstreuen abbildungen. Mathematische Annalen, 97(1):454-472, 1927. URL: http://dx.doi.org/10.1007/BF01447877.
  31. Yue Wang, Jie Gao, and Joseph S B Mitchell. Boundary recognition in sensor networks by topological methods. In 12th annual conference on Mobile computing and networking, pages 122-133, 2006. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact