The DOI matches its Crossref record; 83 of the 83 references it cites were found in a registry or an index.
A survey of graph layout problems
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
(1979) · Cited by 43,841
Lecture Notes in Computer Science 1205
(1999) · Industrial Robot: An International Journal · doi:10.1108/ir.1999.04926fae.001 · Cited by 38,662
Iterative Methods for Sparse Linear Systems
Saad, Y. (2003) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718003 · Cited by 13,790
Bollobás, B. (1985) · Cited by 6,196
Glover, F., & Laguna, M. (1997) · Cited by 5,679
An Efficient Heuristic Procedure for Partitioning Graphs
Kernighan, B. W., & Lin, S. (1970) · Bell System Technical Journal · doi:10.1002/j.1538-7305.1970.tb01770.x · Cited by 5,305
Ford, D. R., & Fulkerson, D. R. (1962) · Cited by 4,072
Algorithmic Graph Theory and Perfect Graphs
(2004) · Annals of Discrete Mathematics · doi:10.1016/s0167-5060(04)x8001-8 · Cited by 3,729
(2011) · SpringerReference · doi:10.1007/springerreference_57547 · Cited by 3,190
Glover, F., & Laguna, M. (1997) · doi:10.1007/978-1-4615-6089-0 · Cited by 3,001
Fellows, M. R. (2002) · Electronic Notes in Theoretical Computer Science · doi:10.1016/s1571-0661(04)00301-9 · Cited by 2,836
Downey, R. G., & Fellows, M. R. (1999) · Monographs in Computer Science · doi:10.1007/978-1-4612-0515-9 · Cited by 2,532
Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
Leighton, F. T. (1991) · CERN Document Server (European Organization for Nuclear Research) · Cited by 2,460
Łuczak, T., Janson, S., & Ruciński, A. (2000) · Cited by 2,192
Some simplified NP-complete graph problems
Garey, M. R., Johnson, D. S., & Stockmeyer, L. (1976) · Theoretical Computer Science · doi:10.1016/0304-3975(76)90059-1 · Cited by 2,059
Local Search in Combinatorial Optimization
(2003) · Princeton University Press eBooks · doi:10.1515/9780691187563 · Cited by 2,057
Proceedings of the 56th Annual ACM Symposium on Theory of Computing
(2024) · doi:10.1145/3618260 · Cited by 1,730
Optimization, approximation, and complexity classes
Papadimitriou, C. H., & Yannakakis, M. (1991) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(91)90023-x · Cited by 1,653
Janson, S., Łuczak, T., & Rucinski, A. (2000) · Wiley eBooks · doi:10.1002/9781118032718 · Cited by 1,545
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
Bodlaender, H. L. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793251219 · Cited by 1,542
Reducing the bandwidth of sparse symmetric matrices
Cuthill, E., & McKee, J. (1969) · Proceedings of the 1969 24th national conference on - · doi:10.1145/800195.805928 · Cited by 1,457
Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning
Johnson, D. S., Aragon, C. R., McGeoch, L. A., & Schevon, C. (1989) · Operations Research · doi:10.1287/opre.37.6.865 · Cited by 1,457
A Separator Theorem for Planar Graphs
Lipton, R. J., & Tarjan, R. E. (1979) · SIAM Journal on Applied Mathematics · doi:10.1137/0136016 · Cited by 1,359
(2000) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(00)90183-4 · Cited by 1,263
Proceedings 35th Annual Symposium on Foundations of Computer Science
(1994) · doi:10.1109/sfcs.1994 · Cited by 1,087
Ausiello, G., Marchetti-Spaccamela, A., Crescenzi, P., Gambosi, G., Protasi, M., & Kann, V. (1999) · Springer eBooks · doi:10.1007/978-3-642-58412-1 · Cited by 979
The shortest path through many points
Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959) · Mathematical Proceedings of the Cambridge Philosophical Society · doi:10.1017/s0305004100034095 · Cited by 937
Ford, L. R., & Fulkerson, D. R. (1963) · Princeton University Press eBooks · doi:10.1515/9781400875184 · Cited by 891
λ1, Isoperimetric inequalities for graphs, and superconcentrators
Alon, N., & Milman, V. D. (1985) · Journal of Combinatorial Theory, Series B · doi:10.1016/0095-8956(85)90092-9 · Cited by 839
Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
Leighton, T., & Rao, S. (1999) · Journal of the ACM · doi:10.1145/331524.331526 · Cited by 820
Vazirani, V. V. (2003) · Springer eBooks · doi:10.1007/978-3-662-04565-7 · Cited by 716
Johnson, D. S., Papadimitriou, C. H., & Yannakakis, M. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90046-3 · Cited by 705
The Chaco user`s guide. Version 1.0
Hendrickson, B., & Leland, R. (1993) · doi:10.2172/10106339 · Cited by 655
An Algorithm for Reducing the Bandwidth and Profile of a Sparse Matrix
Gibbs, N. E., Poole, W. G., & Stockmeyer, P. K. (1976) · SIAM Journal on Numerical Analysis · doi:10.1137/0713023 · Cited by 595
Graph theory, combinatorics, and applications
Alavi, Y., Chartrand, G., & Oellermann, O. R. (2017) · Cited by 520
Barnard, S. T., & Simon, H. D. (1994) · Concurrency: Practice and Experience · doi:10.1002/cpe.4330060203 · Cited by 488
A framework for solving VLSI graph layout problems
Bhatt, S. N., & Leighton, F. T. (1984) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(84)90071-0 · Cited by 438
Algorithms for graph partitioning on the planted partition model
Condon, A., & Karp, R. M. (2001) · Random Structures and Algorithms · doi:10.1002/1098-2418(200103)18:2<116::aid-rsa1001>3.0.co;2-2 · Cited by 429
Limits to parallel computation: P-completeness theory
(1996) · Choice Reviews Online · doi:10.5860/choice.33-3959 · Cited by 412
The NP-Completeness of the bandwidth minimization problem
Papadimitriou, C. H. (1976) · Computing · doi:10.1007/bf02280884 · Cited by 407
The complexity of the network design problem
Johnson, D. S., Lenstra, J. K., & Kan, A. H. G. R. (1978) · Networks · doi:10.1002/net.3230080402 · Cited by 403
Call routing and the ratcatcher
Seymour, P. D., & Thomas, R. (1994) · Combinatorica · doi:10.1007/bf01215352 · Cited by 394
Spectral partitioning works: planar graphs and finite element meshes
Spielman, D. A., & Teng, S.-H. (1996) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548468 · Cited by 393
Graph bisection algorithms with good average case behavior
Bui, T. N., Chaudhuri, S., Leighton, F. T., & Sipser, M. (1987) · Combinatorica · doi:10.1007/bf02579448 · Cited by 323
25th Annual Symposium on Foundations of Computer Science
(1985) · IEEE Software · doi:10.1109/ms.1985.231038 · Cited by 305
Simple Local Search Problems that are Hard to Solve
Schäffer, A. A. (1991) · SIAM Journal on Computing · doi:10.1137/0220004 · Cited by 291
How Good is Recursive Bisection?
Simon, H. D., & Teng, S.-H. (1997) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827593255135 · Cited by 224
Polynomial Time Approximation Schemes for Dense Instances of NP-Hard Problems
Arora, S., Karger, D., & Karpinski, M. (1999) · Journal of Computer and System Sciences · doi:10.1006/jcss.1998.1605 · Cited by 199
Kaplan, H. Y., Ron Shamir, A., & Tarjan, R. E. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539796303044 · Cited by 194
Complexity and algorithms for reasoning about time: a graph-theoretic approach
Golumbic, M. C., & Shamir, R. (1993) · Journal of the ACM · doi:10.1145/174147.169675 · Cited by 188
Incidence matrices, interval graphs and seriation in archeology
Kendall, D. G. (1969) · Pacific Journal of Mathematics · doi:10.2140/pjm.1969.28.565 · Cited by 188
Four Strikes Against Physical Mapping of DNA
Goldberg, P. W., Golumbic, M. C., Kaplan, H. Y., & Ron Shamir, A. (1995) · Journal of Computational Biology · doi:10.1089/cmb.1995.2.139 · Cited by 185
The regularity lemma and approximation schemes for dense problems
Frieze, A., & Kannan, R. (2002) · Proceedings of 37th Conference on Foundations of Computer Science · doi:10.1109/sfcs.1996.548459 · Cited by 170
[Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science
(1988) · doi:10.1109/sfcs.1988 · Cited by 168
A spectral algorithm for envelope reduction of sparse matrices
Barnard, S. T., Pothen, A., & Simon, H. (1995) · Numerical Linear Algebra with Applications · doi:10.1002/nla.1680020402 · Cited by 158
Eigenvalues in Combinatorial Optimization
Mohar, B., & Poljak, S. (1993) · The IMA volumes in mathematics and its applications · doi:10.1007/978-1-4613-8354-3_5 · Cited by 140
30th Annual Symposium on Foundations of Computer Science
(1989) · doi:10.1109/sfcs.1989 · Cited by 134
A Polynomial-Time Approximation Scheme for Minimum Routing Cost Spanning Trees
Wu, B. Y., Lancia, G., Bafna, V., Chao, K., Ravi, R., & Tang, C. Y. (2000) · SIAM Journal on Computing · doi:10.1137/s009753979732253x · Cited by 132
Mapping the genome: some combinatorial problems arising in molecular biology
Karp, R. M. (1993) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/167088.167170 · Cited by 131
An automatic reordering scheme for simultaneous equations derived from network systems
King, I. P. (1970) · International Journal for Numerical Methods in Engineering · doi:10.1002/nme.1620020406 · Cited by 124
A Minimum Linear Arrangement Algorithm for Undirected Trees
Shiloach, Y. (1979) · SIAM Journal on Computing · doi:10.1137/0208002 · Cited by 123
Optimal Numberings of an $N \times N$ Array
Mitchison, G., & Durbin, R. M. (1986) · SIAM Journal on Algebraic and Discrete Methods · doi:10.1137/0607063 · Cited by 118
Greedy, prohibition, and reactive heuristics for graph partitioning
Battiti, R., & Bertossi, A. A. (1999) · IEEE Transactions on Computers · doi:10.1109/12.762522 · Cited by 116
Stack and Queue Layouts of Directed Acyclic Graphs: Part I
Heath, L. S., Pemmaraju, S. V., & Trenk, A. N. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539795280287 · Cited by 115
Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
Kaplan, H. Y., & Ron Shamir, A. (1996) · SIAM Journal on Computing · doi:10.1137/s0097539793258143 · Cited by 113
A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
Lai, Y., & Williams, K. L. (1999) · Journal of Graph Theory · doi:10.1002/(sici)1097-0118(199906)31:2 · Cited by 110
Cluster analysis for hypertext systems
Botafogo, R. A. (1993) · International ACM SIGIR Conference on Research and Development in Information Retrieval (SIGIR) · doi:10.1145/160688.160704 · Cited by 99
Exact and Approximate Solutions for the Gate Matrix Layout Problem
Deo, N., Krishnamoorthy, M. S., & Langston, M. A. (1987) · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · doi:10.1109/tcad.1987.1270248 · Cited by 82
Arora, S., FRIEZE, A. M., & Kaplan, H. Y. (2002) · Annual Symposium on Foundations of Computer Science · doi:10.1109/sfcs.1996.548460 · Cited by 80
Approximating Layout Problems on Random Geometric Graphs
Díaz, J., Penrose, M. D., Petit, J., & Serna, M. (2001) · Journal of Algorithms · doi:10.1006/jagm.2000.1149 · Cited by 66
Self-citationStack and Queue Layouts of Directed Acyclic Graphs: Part II
Heath, L. S., & Pemmaraju, S. V. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539795291550 · Cited by 66
Computing the Bandwidth of Interval Graphs
Kleitman, D. J., & Vohra, R. (1990) · SIAM Journal on Discrete Mathematics · doi:10.1137/0403033 · Cited by 64
On Weighted vs Unweighted Versions of Combinatorial Optimization Problems
Crescenzi, P., Silvestri, R., & Trevisan, L. (2001) · Information and Computation · doi:10.1006/inco.2000.3011 · Cited by 54
Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems
Blum, A. L., Konjevod, G., Ravi, R., & Vempala, S. (2000) · Theoretical Computer Science · doi:10.1016/s0304-3975(99)00181-4 · Cited by 38
An $O( n \log n )$ Algorithm for Bandwidth of Interval Graphs
Sprague, A. (1994) · SIAM Journal on Discrete Mathematics · doi:10.1137/s0895480192232333 · Cited by 35
On the Probable Performance of Heuristics for Bandwidth Minimization
Turner, J. (1986) · SIAM Journal on Computing · doi:10.1137/0215041 · Cited by 32
On finding the minimum bandwidth of interval graphs
Mahesh, R., Rangan, C. P., & Srinivasan, A. (1991) · Information and Computation · doi:10.1016/0890-5401(91)90045-4 · Cited by 26
Finding the minimum bandwidth of an interval graph
Kratsch, D. (1987) · Information and Computation · doi:10.1016/0890-5401(87)90028-9 · Cited by 24
Dı́az, J. (1992) · Lecture notes in computer science · doi:10.1007/3-540-55808-x_2 · Cited by 19
Self-citationTopics in black-box combinatorial optimization
Juels, A., & Sinclair, A. (1996) · Cited by 17
Bandwidth, edgesum and profile of graphs
Lai, Y. (1997) · ScholarWorks - WMU (Western Michigan University) · Cited by 6
Parallel Computing of Physical Maps— A Comparative Study in SIMD and MIMD Parallelism
Bhandarkar, S. M., Chirravuri, S., & Arnold, J. (1996) · Journal of Computational Biology · doi:10.1089/cmb.1996.3.503 · Cited by 6
Cited by
Schaeffer, S. E. (2007) · Computer Science Review · doi:10.1016/j.cosrev.2007.05.001 · Cited by 1,639
Visual Analysis of Large Graphs: State‐of‐the‐Art and Future Research Challenges
von Landesberger, T., Kuijper, A., Schreck, T., Kohlhammer, J., van Wijk, J. J., Fekete, J. ‐., & Fellner, D. W. (2011) · Computer Graphics Forum · doi:10.1111/j.1467-8659.2011.01898.x · Cited by 515
Baronchelli, A., Ferrer-i-Cancho, R., Pastor-Satorras, R., Chater, N., & Christiansen, M. H. (2013) · Trends in Cognitive Sciences · doi:10.1016/j.tics.2013.04.010 · Cited by 333
Centrality Measures Based on Current Flow
Brandes, U., & Fleischer, D. (2005) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-31856-9_44 · Cited by 333
Parameterized Complexity and Approximation Algorithms
Marx, D. (2007) · The Computer Journal · doi:10.1093/comjnl/bxm048 · Cited by 283
Metadata
- Authors
- Díaz, J., Petit, J., & Serna, M.
- Venue
- ACM Computing Surveys
- Published
- 2002-09
- Volume
- 34
- Issue
- 3
- Pages
- 313-356
- ISSN
- 0360-0300 (ISSN-L)
- 1557-7341
- OpenAlex
- W2079966248
- Cited by
- 599
- References
- 83
- FWCI
- 24.66
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.