Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area

Maarten Löffler

doi:10.4230/LIPIcs.GD.2024.47

Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area

Maarten Löffler^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

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	https://doi.org/10.4230/LIPIcs.GD.2024.47
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

Access to Document

10.4230/LIPIcs.GD.2024.47Licence: CC BY

LIPIcs.GD.2024.47Final published version, 569 KBLicence: CC BY

Cite this

@inproceedings{706a93d1254b492d8b47026e34cdeb43,

title = "Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area",

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.",

keywords = "grid drawings, minimal area, Upward drawings",

author = "Maarten L{\"o}ffler",

note = "Publisher Copyright: {\textcopyright} Maarten L{\"o}ffler.; 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024 ; Conference date: 18-09-2024 Through 20-09-2024",

year = "2024",

month = oct,

day = "28",

doi = "10.4230/LIPIcs.GD.2024.47",

language = "English",

series = "Leibniz International Proceedings in Informatics, LIPIcs",

publisher = "Dagstuhl Publishing",

editor = "Stefan Felsner and Karsten Klein",

booktitle = "32nd International Symposium on Graph Drawing and Network Visualization, GD 2024",

}

Löffler, M 2024, Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area. in S Felsner & K Klein (eds), 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024., 47, Leibniz International Proceedings in Informatics, LIPIcs, vol. 320, Dagstuhl Publishing, 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024, Vienna, Austria, 18/09/24. https://doi.org/10.4230/LIPIcs.GD.2024.47

Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area. / Löffler, Maarten.
32nd International Symposium on Graph Drawing and Network Visualization, GD 2024. ed. / Stefan Felsner; Karsten Klein. Dagstuhl Publishing, 2024. 47 (Leibniz International Proceedings in Informatics, LIPIcs; Vol. 320).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area

AU - Löffler, Maarten

PY - 2024/10/28

Y1 - 2024/10/28

N2 - 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.

AB - 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.

KW - grid drawings

KW - minimal area

KW - Upward drawings

UR - https://www.scopus.com/pages/publications/85208809229

U2 - 10.4230/LIPIcs.GD.2024.47

DO - 10.4230/LIPIcs.GD.2024.47

M3 - Conference contribution

AN - SCOPUS:85208809229

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

A2 - Felsner, Stefan

A2 - Klein, Karsten

PB - Dagstuhl Publishing

T2 - 32nd International Symposium on Graph Drawing and Network Visualization, GD 2024

Y2 - 18 September 2024 through 20 September 2024

ER -

Strict Upward Planar Grid Drawings of Binary Trees with Minimal Area

Abstract

Publication series

Conference

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this