Unit-length embedding of binary trees on a square grid

DOI10.1016/0020-0190(89)90118-XMaRDI QIDQ1120274zbMATH OpenOpenAlexFDO

Authors 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 treegraph embeddingNP-completenessVLSI layoutwire length

Mathematics Subject Classification ID

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

Recommendations

• How to fit a tree in a box
• How to fit a tree in a box
• NP-completeness for minimizing maximum edge length in grid embeddings
• Complexity dichotomy on partial grid recognition
• Optimal embedding of complete binary trees into lines and grids

Cites work

• The complexity of minimizing wire lengths in VLSI layouts

Cited in

(19)

• The logic engine and the realization problem for nearest neighbor graphs
• Expansion of layouts of complete binary trees into grids
• On the complexity of drawing trees nicely: Corrigendum
• The realization problem for Euclidean minimum spanning trees is NP-hard
• Complexity dichotomy on degree-constrained VLSI layouts with unit-length edges
• A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs
• Satisfiability for SCULPT-schemas for CSV-like data
• scientific article; zbMATH DE number 3945345 (Why is no real title available?)
• On upward drawings of trees on a given grid
• Nearest neighbour graph realizability is NP-hard
• Complexity dichotomy on partial grid recognition
• How to fit a tree in a box
• How to fit a tree in a box
• scientific article; zbMATH DE number 7765365 (Why is no real title available?)
• Unit-length rectangular drawings of graphs
• Grid recognition: classical and parameterized computational perspectives
• Unit-length rectangular drawings of graphs
• On the complexity of embedding in graph products
• Drawn tree decomposition: new approach for graph drawing problems

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1120274)