Graph graphics: Theory and practice
From MaRDI portal
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.
Recommendations
Cites work
- A framework for solving VLSI graph layout problems
- A linear algorithm for embedding planar graphs using PQ-trees
- Computing an st-numbering
- Crossing Number is NP-Complete
- Efficient Planarity Testing
- Graph theoretic foundations of pathfinder networks
- How to Draw a Graph
- scientific article; zbMATH DE number 3648730 (Why is no real title available?)
- scientific article; zbMATH DE number 3858396 (Why is no real title available?)
- scientific article; zbMATH DE number 3315017 (Why is no real title available?)
- NP-completeness for minimizing maximum edge length in grid embeddings
- Parallel concepts in graph theory
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Cited in
(26)- Heuristics for laying out information graphs
- Algorithms for drawing graphs: An annotated bibliography
- Constraints in graph drawing algorithms
- One-sided weak dominance drawing
- Special issue: graph drawing
- Parameterized analysis and crossing minimization problems
- Drawing borders efficiently
- A framework and algorithms for circular drawings of graphs
- Graph drawing: The aesthetics-complexity trade-off
- Planar drawing algorithms of survivable telecommunication networks
- A contribution to the study of the fitness landscape for a graph drawing problem
- The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings
- Drawing graphs within restricted area
- scientific article; zbMATH DE number 2123123 (Why is no real title available?)
- scientific article; zbMATH DE number 3860848 (Why is no real title available?)
- The Galois complexity of graph drawing: why numerical solutions are ubiquitous for force-directed, spectral, and circle packing drawings
- scientific article; zbMATH DE number 1182937 (Why is no real title available?)
- Graph layout for displaying data structures
- scientific article; zbMATH DE number 1424309 (Why is no real title available?)
- Drawing Borders Efficiently
- Recent advances in graph drawing
- Generalizing geometric graphs
- Generalizing geometric graphs
- On the complexity of the Edge Label Placement problem
- The Computational Complexity of the ChordLink Model
- Drawing graphs by eigenvectors: theory and practice
This page was built for publication: Graph graphics: Theory and practice
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1103411)