A survey of graph layout problems
Top Cited Papers
- 1 September 2002
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Computing Surveys
- Vol. 34 (3) , 313-356
- https://doi.org/10.1145/568522.568523
Abstract
Graph layout problems are a particular class of combinatorial optimization problems whose goal is to find a linear layout of an input graph in such way that a certain objective cost is optimized. This survey considers their motivation, complexity, approximation properties, upper and lower bounds, heuristics and probabilistic analysis on random graphs. The result is a complete view of the current state of the art with respect to layout problems from an algorithmic point of view.Keywords
This publication has 157 references indexed in Scilit:
- Some simplified NP-complete graph problemsPublished by Elsevier ,2002
- The bisection width of grid graphsTheory of Computing Systems, 1996
- COMBINING HELPFUL SETS AND PARALLEL SIMULATED ANNEALING FOR THE GRAPH-PARTITIONING PROBLEM∗Parallel Algorithms and Applications, 1996
- Packing directed circuits fractionallyCombinatorica, 1995
- On search, decision, and the efficiency of polynomial-time algorithmsJournal of Computer and System Sciences, 1994
- Call routing and the ratcatcherCombinatorica, 1994
- Edge-isoperimetric inequalities in the gridCombinatorica, 1991
- A framework for solving VLSI graph layout problemsJournal of Computer and System Sciences, 1984
- The complexity of the network design problemNetworks, 1978
- Optimal labelling of a product of two pathsDiscrete Mathematics, 1975