Graph graphics: Theory and practice
type: Item
instance of: scholarly article
title: Graph graphics: Theory and practice
zbMATH Open document ID: 0645.68079
DOI: 10.1016/0898-1221(88)90208-8
author: B. George
publication date: 1988-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68U99
zbMATH DE Number: 4053044
zbMATH Keywords: polynomial-time algorithms
zbMATH Keywords: graph drawing
zbMATH Keywords: expository survey
zbMATH Keywords: complexity
zbMATH Keywords: graph layout
zbMATH Keywords: VLSI
MaRDI profile type: Publication
full work available at URL: 0898-1221(88)90208-8
OpenAlex ID: W2085219981
cites work: Parallel concepts in graph theory
cites work: A framework for solving VLSI graph layout problems
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: Efficient Planarity Testing
cites work: Crossing Number is NP-Complete
cites work: Graph theoretic foundations of pathfinder networks
cites work: NP-completeness for minimizing maximum edge length in grid embeddings
cites work: Q3206972
cites work: Q3326832
cites work: How to Draw a Graph
cites work: Q5596083
cites work: Computing an st-numbering
cites work: A linear algorithm for embedding planar graphs using PQ-trees
published in: Computers & Mathematics with Applications
description: scientific article; zbMATH DE number 4053044