Graph graphics: Theory and practice (Q1103411)

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.