NP-completeness for minimizing maximum edge length in grid embeddings
From MaRDI portal
Publication:3677185
DOI10.1016/0196-6774(85)90016-1zbMath0563.68058OpenAlexW2117771589WikidataQ59592734 ScholiaQ59592734MaRDI QIDQ3677185
No author found.
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90016-1
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Graph graphics: Theory and practice ⋮ The complexity of minimizing wire lengths in VLSI layouts ⋮ The realization problem for Euclidean minimum spanning trees is NP-hard ⋮ Lattice bandwidth of random graphs
