Abstract
Given a rooted binary tree T and a tuple (w, h), we wish to test whether there exists a strict upward drawing of T on a w × h grid; that is, a planar grid drawing with straight-line edges where every vertex has a strictly lower y-coordinate than its parent. Biedl and Mondal [2] prove that this problem is NP-hard for general trees; their construction crucially uses nodes of very high degree. Akatiya et al [1] prove that the problem is also NP-hard for binary trees with a fixed combinatorial embedding; their construction crucially relies on the fixed embedding. Both pose the question for binary trees and a free embedding as an open problem. Here, we show that this problem is also NP-hard.
| Original language | English |
|---|---|
| Title of host publication | 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024 |
| Editors | Stefan Felsner, Karsten Klein |
| Publisher | Dagstuhl Publishing |
| Number of pages | 3 |
| ISBN (Electronic) | 9783959773430 |
| DOIs | |
| Publication status | Published - 28 Oct 2024 |
| Event | 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024 - Vienna, Austria Duration: 18 Sept 2024 → 20 Sept 2024 |
Publication series
| Name | Leibniz International Proceedings in Informatics, LIPIcs |
|---|---|
| Volume | 320 |
| ISSN (Print) | 1868-8969 |
Conference
| Conference | 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024 |
|---|---|
| Country/Territory | Austria |
| City | Vienna |
| Period | 18/09/24 → 20/09/24 |
Bibliographical note
Publisher Copyright:© Maarten Löffler.
Keywords
- grid drawings
- minimal area
- Upward drawings