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

Tim Ophelders, Salman Parsa

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

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,? R 2 as follows. For a vertical line l in R 2, let the height of l be the cardinality of the set l n ?(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.

Original languageEnglish
Title of host publication38th International Symposium on Computational Geometry, SoCG 2022
EditorsXavier Goaoc, Michael Kerber
Pages55:1-55:16
ISBN (Electronic)9783959772273
DOIs
Publication statusPublished - 1 Jun 2022
EventInternational Symposium on Computational Geometry - Berlin, Germany
Duration: 7 Jun 202210 Jun 2022
Conference number: 38

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume224
ISSN (Print)1868-8969

Conference

ConferenceInternational Symposium on Computational Geometry
Abbreviated titleSoCG
Country/TerritoryGermany
CityBerlin
Period7/06/2210/06/22

Bibliographical note

DBLP's bibliographic metadata records provided through http://dblp.org/search/publ/api are distributed under a Creative Commons CC0 1.0 Universal Public Domain Dedication. Although the bibliographic metadata records are provided consistent with CC0 1.0 Dedication, the content described by the metadata records is not. Content may be subject to copyright, rights of privacy, rights of publicity and other restrictions.

Keywords

  • Graph drawing
  • homotopy height

Fingerprint

Dive into the research topics of 'Minimum Height Drawings of Ordered Trees in Polynomial Time: Homotopy Height of Tree Duals.'. Together they form a unique fingerprint.

Cite this