Graph graphics: Theory and practice (Q1103411): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1016/0898-1221(88)90208-8 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2085219981 / rank | |||
Normal rank | |||
Revision as of 22:43, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Graph graphics: Theory and practice |
scientific article |
Statements
Graph graphics: Theory and practice (English)
0 references
1988
0 references
Many graph drawing problems are NP-complete. Most of the problems described in this expository survey have constraints that relate to either minimizing the number of crossings or minimizing some function of the edge lengths. A graph-theoretic characterization of some of these problems is given, followed by a discussion of their complexity. Finally, several algorithms and heuristics for graph layout [some with applications to very large scale integration (VLSI)] will be discussed.
0 references
polynomial-time algorithms
0 references
graph drawing
0 references
expository survey
0 references
complexity
0 references
graph layout
0 references
VLSI
0 references
