Document Open Access Logo

Hanani-Tutte for Approximating Maps of Graphs

Authors Radoslav Fulek, Jan Kyncl

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.39.pdf
  • Filesize: 0.68 MB
  • 15 pages

Document Identifiers

Author Details

Radoslav Fulek
Jan Kyncl

Cite As Get BibTex

Radoslav Fulek and Jan Kyncl. Hanani-Tutte for Approximating Maps of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.SoCG.2018.39

Abstract

We resolve in the affirmative conjectures of A. Skopenkov and Repovs (1998), and M. Skopenkov (2003) generalizing the classical Hanani-Tutte theorem to the setting of approximating maps of graphs on 2-dimensional surfaces by embeddings. Our proof of this result is constructive and almost immediately implies an efficient algorithm for testing whether a given piecewise linear map of a graph in a surface is approximable by an embedding. More precisely, an instance of this problem consists of (i) a graph G whose vertices are partitioned into clusters and whose inter-cluster edges are partitioned into bundles, and (ii) a region R of a 2-dimensional compact surface M given as the union of a set of pairwise disjoint discs corresponding to the clusters and a set of pairwise disjoint "pipes" corresponding to the bundles, connecting certain pairs of these discs. We are to decide whether G can be embedded inside M so that the vertices in every cluster are drawn in the corresponding disc, the edges in every bundle pass only through its corresponding pipe, and every edge crosses the boundary of each disc at most once.

Subject Classification

Keywords
  • Hanani-Tutte theorem
  • graph embedding
  • map approximation
  • weak embedding
  • clustered planarity

Metrics

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

References

  1. Hugo A. Akitaya, Greg Aloupis, Jeff Erickson, and Csaba Tóth. Recognizing weakly simple polygons. In 32nd International Symposium on Computational Geometry (SoCG 2016), volume 51 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1-8:16, 2016. Google Scholar
  2. Hugo A. Akitaya, Radoslav Fulek, and Csaba D. Tóth. Recognizing weak embeddings of graphs. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 274-292, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.20.
  3. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, and Fabrizio Frati. Strip planarity testing for embedded planar graphs. Algorithmica, 77(4):1022-1059, 2017. Google Scholar
  4. Patrizio Angelini, Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, and Ignaz Rutter. Beyond Level Planarity, pages 482-495. Springer International Publishing, Cham, 2016. Google Scholar
  5. Patrizio Angelini and Giordano Da Lozzo. Clustered Planarity with Pipes. In Seok-Hee Hong, editor, 27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 of Leibniz International Proceedings in Informatics (LIPIcs), pages 13:1-13:13, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2016.13.
  6. Therese C. Biedl. Drawing planar partitions III: Two constrained embedding problems, 1998. Google Scholar
  7. Hsien-Chih Chang, Jeff Erickson, and Chao Xu. Detecting weakly simple polygons. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1655-1670. SIAM, Philadelphia, PA, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.110.
  8. F. Cortese and G. Di Battista. Clustered planarity (invited lecture). In Twenty-first annual symposium on Computational Geometry (proc. SoCG 05), pages 30-32, 2005. Google Scholar
  9. Pier Francesco Cortese, Giuseppe Di Battista, Maurizio Patrignani, and Maurizio Pizzonia. On embedding a cycle in a plane graph. Discrete Math., 309(7):1856-1869, 2009. URL: http://dx.doi.org/10.1016/j.disc.2007.12.090.
  10. Qing-Wen Feng, Robert F. Cohen, and Peter Eades. How to draw a planar clustered graph. In Computing and combinatorics (Xi'an, 1995), volume 959 of Lecture Notes in Comput. Sci., pages 21-30. Springer, Berlin, 1995. URL: http://dx.doi.org/10.1007/BFb0030816.
  11. Qing-Wen Feng, Robert F. Cohen, and Peter Eades. Planarity for clustered graphs. In Algorithms - ESA '95, volume 979 of Lecture Notes in Comput. Sci., pages 213-226. Springer Berlin Heidelberg, 1995. Google Scholar
  12. Radoslav Fulek. Embedding graphs into embedded graphs. In 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand, pages 34:1-34:12, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ISAAC.2017.34.
  13. Radoslav Fulek, Jan Kynčl, Igor Malinović, and Dömötör Pálvölgyi. Clustered planarity testing revisited. Electron. J. Combin., 22(4):Paper 4.24, 29 pp., 2015. Google Scholar
  14. Radoslav Fulek, Jan Kynčl, and Dömötör Pálvölgyi. Unified Hanani-Tutte theorem. Electr. J. Comb., 24(3):P3.18, 2017. URL: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p18.
  15. Radoslav Fulek, Michael Pelsmajer, and Marcus Schaefer. Hanani-Tutte for radial planarity II. In Yifan Hu and Martin Nöllenburg, editors, Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, pages 468-481, Cham, 2016. Springer International Publishing. Google Scholar
  16. Radoslav Fulek, Michael Pelsmajer, and Marcus Schaefer. Hanani-Tutte for radial planarity. Journal of Graph Algorithms and Applications, 21(1):135-154, 2017. Google Scholar
  17. Radoslav Fulek, Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Hanani-Tutte, monotone drawings, and level-planarity. In Thirty essays on geometric graph theory, pages 263-287. Springer, New York, 2013. URL: http://dx.doi.org/10.1007/978-1-4614-0110-0_14.
  18. François Le Gall. Powers of tensors and fast matrix multiplication. http://arxiv.org/abs/1401.7714, 2014.
  19. Carsten Gutwenger, Michael Jünger, Sebastian Leipert, Petra Mutzel, Merijam Percan, and René Weiskircher. Advances in c-planarity testing of clustered graphs. In Michael T. Goodrich and Stephen G. Kobourov, editors, Graph Drawing: 10th International Symposium, GD 2002 Irvine, CA, USA, August 26-28, 2002 Revised Papers, pages 220-236, Berlin, Heidelberg, 2002. Springer Berlin Heidelberg. URL: http://dx.doi.org/10.1007/3-540-36151-0_21.
  20. Haim Hanani. Über wesentlich unplättbare Kurven im drei-dimensionalen Raume. Fundamenta Mathematicae, 23:135-142, 1934. Google Scholar
  21. Seok hee Hong and Hiroshi Nagamochi. Two-page book embedding and clustered graph planarity. Theoretical Computing Science, 2016. Google Scholar
  22. John Hopcroft and Robert Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974. Google Scholar
  23. Piotr Minc. Embedding of simplicial arcs into the plane. Topology Proc., 22(Summer):305-340, 1997. Google Scholar
  24. Bojan Mohar. A linear time algorithm for embedding graphs in an arbitrary surface. SIAM J. Discrete Math., 12(1):6-26, 1999. Google Scholar
  25. Bojan Mohar and Carsten Thomassen. Graphs on surfaces. Johns Hopkins University Pres, 2001. Google Scholar
  26. Michael J. Pelsmajer, Marcus Schaefer, and Daniel Štefankovič. Removing even crossings. J. Combin. Theory Ser. B, 97(4):489-500, 2007. Google Scholar
  27. Dušan Repovš and Arkadij B. Skopenkov. A deleted product criterion for approximability of maps by embeddings. Topology Appl., 87(1):1-19, 1998. URL: http://dx.doi.org/10.1016/S0166-8641(97)00121-1.
  28. Marcus Schaefer. Hanani-Tutte and related results. In Geometry - intuitive, discrete, and convex, volume 24 of Bolyai Soc. Math. Stud., pages 259-299. János Bolyai Math. Soc., Budapest, 2013. Google Scholar
  29. Marcus Schaefer. Toward a theory of planarity: Hanani-Tutte and planarity variants. J. Graph Algorithms Appl., 17(4):367-440, 2013. URL: http://dx.doi.org/10.7155/jgaa.00298.
  30. Mikhail Skopenkov. On approximability by embeddings of cycles in the plane. Topology Appl., 134(1):1-22, 2003. URL: http://dx.doi.org/10.1016/S0166-8641(03)00069-5.
  31. Carsten Thomassen. The graph genus problem is NP-complete. Journal of Algorithms, 10(4):568-576, 1989. URL: http://dx.doi.org/10.1016/0196-6774(89)90006-0.
  32. W. T. Tutte. Toward a theory of crossing numbers. J. Combinatorial Theory, 8:45-53, 1970. Google Scholar
  33. Douglas H. Wiedemann. Solving sparse linear equations over finite fields. IEEE Trans. Inform. Theory, 32(1):54-62, 1986. URL: http://dx.doi.org/10.1109/TIT.1986.1057137.
  34. Virginia Vassilevska Williams. Multiplying matrices faster than Coppersmith-Winograd. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 887-898, 2012. 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