On Upward Drawings of Trees on a Given Grid

Biedl, Therese and Mondal, Debajyoti (2017) On Upward Drawings of Trees on a Given Grid. In: Graph Drawing and Network Visualization. GD 2017, September 25-27 , pp. 318-325(Official URL: https://doi.org/10.1007/978-3-319-73915-1_25).

Full text not available from this repository.


Computing a minimum-area planar straight-line drawing of a graph is known to be NP-hard for planar graphs, even when restricted to outerplanar graphs. However, the complexity question is open for trees. Only a few hardness results are known for straight-line drawings of trees under various restrictions such as edge length or slope constraints. On the other hand, there exist polynomial-time algorithms for computing minimum-width (resp., minimum-height) upward drawings of trees, where the height (resp., width) is unbounded. In this paper we take a major step in understanding the complexity of the area minimization problem for strictly-upward drawings of trees, which is one of the most common styles for drawing rooted trees. We prove that given a rooted tree T and a W×H grid, it is NP-hard to decide whether T admits a strictly-upward (unordered) drawing in the given grid. The hardness result holds both in polyline and straight-line drawing settings.

Item Type: Conference Paper
Classifications: M Methods > M.900 Tree
P Styles > P.720 Straight-line
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1612

Actions (login required)

View Item View Item