Document Open Access Logo

Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals

Authors Tim Ophelders , Salman Parsa

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.55.pdf
  • Filesize: 0.95 MB
  • 16 pages

Document Identifiers

Author Details

Tim Ophelders
  • Department of Information and Computing Science, Utrecht University, The Netherlands
  • Department of Mathematics and Computer Science, TU Eindhoven, The Netherlands
Salman Parsa
  • Scientific Computing and Imaging Institute, University of Utah, Salt Lake City, UT, USA

Funding

  • Ophelders, Tim: This author was supported by the Dutch Research Council (NWO) under project no. VI.Veni.212.260.
  • Parsa, Salman: This author was funded in part by the SLU Research Institute and by NSF grant CCF-1614562.

Cite As Get BibTex

Tim Ophelders and Salman Parsa. Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022) https://doi.org/10.4230/LIPIcs.SoCG.2022.55

Abstract

We consider drawings of graphs in the plane in which vertices are assigned distinct points in the plane and edges are drawn as simple curves connecting the vertices and such that the edges intersect only at their common endpoints. There is an intuitive quality measure for drawings of a graph that measures the height of a drawing ϕ : G↪ℝ² as follows. For a vertical line 𝓁 in ℝ², let the height of 𝓁 be the cardinality of the set 𝓁 ∩ ϕ(G). The height of a drawing of G is the maximum height over all vertical lines. In this paper, instead of abstract graphs, we fix a drawing and consider plane graphs. In other words, we are looking for a homeomorphism of the plane that minimizes the height of the resulting drawing. This problem is equivalent to the homotopy height problem in the plane, and the homotopic Fréchet distance problem. These problems were recently shown to lie in NP, but no polynomial-time algorithm or NP-hardness proof has been found since their formulation in 2009. We present the first polynomial-time algorithm for drawing trees with optimal height. This corresponds to a polynomial-time algorithm for the homotopy height where the triangulation has only one vertex (that is, a set of loops incident to a single vertex), so that its dual is a tree.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Graph drawing
  • homotopy height

Metrics

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

Related Versions

References

  1. Hugo A Akitaya, Maarten Löffler, and Irene Parada. How to fit a tree in a box. In Proceedings of the 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), pages 361-367. Springer, 2018. Google Scholar
  2. Therese Biedl, Erin Wolf Chambers, David Eppstein, Arnaud de Mesmay, and Tim Ophelders. Homotopy height, grid-major height and graph-drawing height. In Proceedings of the 27th Graph Drawing and Network Visualization (GD 2019), pages 468-481. Springer, 2019. Google Scholar
  3. Benjamin Burton, Erin Chambers, Marc van Kreveld, Wouter Meulemans, Tim Ophelders, and Bettina Speckmann. Computing optimal homotopies over a spiked plane with polygonal boundary. In Proceddings of the 25th Annual European Symposium on Algorithms (ESA), 2017. Google Scholar
  4. Erin Wolf Chambers, Gregory R Chambers, Arnaud de Mesmay, Tim Ophelders, and Regina Rotman. Constructing monotone homotopies and sweepouts. arXiv preprint, 2017. URL: http://arxiv.org/abs/1704.06175.
  5. Erin Wolf Chambers, Arnaud de Mesmay, and Tim Ophelders. On the complexity of optimal homotopies. In Proceedings of the 29th Annual Symposium on Discrete Algorithms (SODA 2018), pages 1121-1134, 2018. Google Scholar
  6. Erin Wolf Chambers and David Letscher. On the height of a homotopy. In Canadian Conference on Computational Geometry (CCCG), volume 9, pages 103-106, 2009. Google Scholar
  7. Moon-Jung Chung, Fillia Makedon, Ivan Hal Sudborough, and Jonathan Turner. Polynomial time algorithms for the min cut problem on degree restricted trees. SIAM Journal on Computing, 14(1):158-177, 1985. Google Scholar
  8. Michael R Garey and David S Johnson. Computers and intractability, volume 174. Freeman San Francisco, 1979. Google Scholar
  9. F Gavril. Some NP-complete problems on graphs. In Proc. Conf. on Inform. Sci. and Systems, 1977, pages 91-95, 1977. Google Scholar
  10. Sariel Har-Peled, Amir Nayyeri, Mohammad Salavatipour, and Anastasios Sidiropoulos. How to walk your dog in the mountains with no magic leash. Discrete & Computational Geometry, 55(1):39-73, 2016. Google Scholar
  11. Thomas Lengauer. Upper and lower bounds on the complexity of the min-cut linear arrangement problem on trees. SIAM Journal on Algebraic Discrete Methods, 3(1):99-113, 1982. Google Scholar
  12. Debajyoti Mondal, Muhammad Jawaherul Alam, and Md. Saidur Rahman. Minimum-layer drawings of trees. In Naoki Katoh and Amit Kumar, editors, WALCOM: Algorithms and Computation, pages 221-232. Springer, 2011. Google Scholar
  13. B. Monien and I.H. Sudborough. Min cut is NP-complete for edge weighted trees. Theoretical Computer Science, 58(1):209-229, 1988. Google Scholar
  14. Yossi Shiloach. A minimum linear arrangement algorithm for undirected trees. SIAM Journal on Computing, 8(1):15-32, 1979. Google Scholar
  15. Mihalis Yannakakis. A polynomial algorithm for the min-cut linear arrangement of trees. Journal of the ACM, 32(4):950-988, 1985. 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