NP-completeness for minimizing maximum edge length in grid embeddings

DOI10.1016/0196-6774(85)90016-1zbMath0563.68058DBLPjournals/jal/MillerO85OpenAlexW2117771589WikidataQ59592734 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

zbMATH Keywords

combinatorial optimizationgraph embeddingstwo-dimensional lattice

Mathematics Subject Classification ID

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 (4)

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

This page was built for publication: NP-completeness for minimizing maximum edge length in grid embeddings