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 polynomialtime algorithm or NPhardness proof has been found since their formulation in 2009. We present the first polynomialtime algorithm for drawing trees with optimal height. This corresponds to a polynomialtime 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.
BibTeX  Entry
@InProceedings{ophelders_et_al:LIPIcs.SoCG.2022.55,
author = {Ophelders, Tim and Parsa, Salman},
title = {{Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {55:155:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16063},
URN = {urn:nbn:de:0030drops160631},
doi = {10.4230/LIPIcs.SoCG.2022.55},
annote = {Keywords: Graph drawing, homotopy height}
}
Keywords: 

Graph drawing, homotopy height 
Collection: 

38th International Symposium on Computational Geometry (SoCG 2022) 
Issue Date: 

2022 
Date of publication: 

01.06.2022 