2026-08-07T09:49:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21331 2024-10-28T09:51:06Z ddc:004 open_access

Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area (Poster Abstract) Löffler, Maarten Upward drawings grid drawings minimal area 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, 2017] prove that this problem is NP-hard for general trees; their construction crucially uses nodes of very high degree. [Akatiya et al., 2018] 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Maarten Löffler 2024 Is Part Of LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.GD.2024.47 urn:nbn:de:0030-drops-213311 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.47 eng https://creativecommons.org/licenses/by/4.0/legalcode