Unit-length embedding of binary trees on a square grid

DOI10.1016/0020-0190(89)90118-XzbMath0672.68014OpenAlexW1967603300MaRDI QIDQ1120274

Angelo Gregori

Publication date: 1989

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(89)90118-x

zbMATH Keywords

binary treeNP-completenessgraph embeddingVLSI layoutwire length

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (13)

Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges ⋮ Unnamed Item ⋮ The logic engine and the realization problem for nearest neighbor graphs ⋮ The realization problem for Euclidean minimum spanning trees is NP-hard ⋮ Nearest neighbour graph realizability is NP-hard ⋮ Unit-length rectangular drawings of graphs ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Expansion of layouts of complete binary trees into grids ⋮ Unnamed Item ⋮ On Upward Drawings of Trees on a Given Grid ⋮ A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs ⋮ Complexity dichotomy on partial grid recognition ⋮ How to fit a tree in a box

Cites Work

• The complexity of minimizing wire lengths in VLSI layouts

This page was built for publication: Unit-length embedding of binary trees on a square grid