We consider minimum height drawings of graphs in the plane.
We define the height of a drawing as the minimum value h such that any vertical line intersects the drawing in at most h points.
Given a simple drawing of a planar graph, 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 computing the homotopy height of triangulations consisting of a single vertex incident to a set of loops.