- 著者
- F. J. Brandenburg
- タイトル
- On the complexity of optimal drawings of graphs
- 書籍
- Graph-Theoretic Concepts in Computer Science: 15th International Workshop WG '89 Proceedings
- ページ
- 166-80
- 日時
- June 1989
- 概要
- Considers the problem of producing aesthetically nice drawings of graphs from the complexity point of view. The author proposes grid embeddings of graphs and measures 'nice' by algorithmic cost measures of the embeddings, e.g., area, expansion, edge length, etc. He proves that optimal embeddings with fixed costs are NP-complete, even for binary trees. This sharpens previous NP-completeness results of optimal embeddings from connected graphs to binary trees and extends them to other cost measures. The author introduces placement graph grammars. These are special graph grammars enriched by a placement component. The placement component contains partial information on the relative positions of the vertices, which is a reduction of the placement information contained in any concrete grid drawing. Every derivation of a graph in the base graph grammar has an associated placement component. By an extension of the parsing process one can compute a placement of the vertices of each generated graph, which is consistent with the associated placement component, and is area minimal. For connected graphs of bounded degree this can be done in polynomial time
- カテゴリ
- GraphLayout

Category: GraphLayout Organization: Lehrstuhl fur Inf., Passau University, West Germany Edited by: Nagl, M. Abstract: Considers the problem of producing aesthetically nice drawings of graphs from the complexity point of view. The author proposes grid embeddings of graphs and measures 'nice' by algorithmic cost measures of the embeddings, e.g., area, expansion, edge length, etc. He proves that optimal embeddings with fixed costs are NP-complete, even for binary trees. This sharpens previous NP-completeness results of optimal embeddings from connected graphs to binary trees and extends them to other cost measures. The author introduces placement graph grammars. These are special graph grammars enriched by a placement component. The placement component contains partial information on the relative positions of the vertices, which is a reduction of the placement information contained in any concrete grid drawing. Every derivation of a graph in the base graph grammar has an associated placement component. By an extension of the parsing process one can compute a placement of the vertices of each generated graph, which is consistent with the associated placement component, and is area minimal. For connected graphs of bounded degree this can be done in polynomial time Bibtype: InProceedings Booktitle: Graph-Theoretic Concepts in Computer Science: 15th International Workshop WG '89 Proceedings Author: F. J. Brandenburg Pages: 166-80 Month: jun Title: On the complexity of optimal drawings of graphs Year: 1989 Keyword: computational complexity, grammars, graph theory, graphs, optimisation, complexity, optimal drawings, graphs, grid embeddings, NP-complete, binary trees, placement graph grammars, parsing