NP-completeness for minimizing maximum edge length in grid embeddings

DOI10.1016/0196-6774(85)90016-1MaRDI QIDQ3677185zbMATH OpenOpenAlexDBLPWikidataFDO

Authors

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

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

• On computational complexity of length embeddability of graphs
• Maximizing edge-ratio is NP-complete
• Approximating the longest paths in grid graphs
• On Embedding a Graph in the Grid with the Minimum Number of Bends
• On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features
• On embedding a graph in the grid with the maximum number of bends and other bad features
• NP-completeness results for edge modification problems
• An NP-completeness result of edge search in graphs
• The minimum shared edges problem on grid-like graphs
• Computing MaxMin edge length triangulations

Cited in

(9)

• Graph graphics: Theory and practice
• The complexity of minimizing wire lengths in VLSI layouts
• Unit-length embedding of binary trees on a square grid
• The realization problem for Euclidean minimum spanning trees is NP-hard
• On computational complexity of length embeddability of graphs
• The hardness of the grid problemGi Under the Routine Resolution Method
• Algorithm Theory - SWAT 2004
• Complexity dichotomy on partial grid recognition
• Lattice bandwidth of random graphs

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

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