- 著者
- F. J. Brandenburg
- タイトル
- Nice drawings of graphs are computationally hard
- ページ
- 1-15
- 日時
- May 1988
- 概要
- The problem of how to draw a graph and more importantly, how to draw it nicely is addressed. As a formal approach to this problem, the author proposes graph embeddings. A graph embedding is a mapping from a guest graph into a host graph. Graph embeddings are very rich in their descriptive capabilities. These should suffice to capture all instances from real applications in an appropriate way. Graph embeddings offer various parameters for optimizations which are used to describe aesthetics in a formal and uniform way. Thus, one measures the niceness of a drawing by the values of its aesthetic parameters, such as area, width, expansion, maximal and total edge length, or non-planarity. However, in this general framework and from an algorithmic point of view, optimal embeddings or equivalently nice drawings of graphs are intractable. In general, they are NP-complete, which means that one must pay for nice drawings with a high computational effort. This fact holds even for trees. To the contrary, there are drawings of trees which satisfy the upper and lower bounds up to some constant factor and are computable in polynomial time
- カテゴリ
- GraphLayout

Category: GraphLayout Organization: Lehrstuhl fur Inf., Passau University, West Germany Edited by: Gorny, P.; Tauber, M.J. Abstract: The problem of how to draw a graph and more importantly, how to draw it nicely is addressed. As a formal approach to this problem, the author proposes graph embeddings. A graph embedding is a mapping from a guest graph into a host graph. Graph embeddings are very rich in their descriptive capabilities. These should suffice to capture all instances from real applications in an appropriate way. Graph embeddings offer various parameters for optimizations which are used to describe aesthetics in a formal and uniform way. Thus, one measures the niceness of a drawing by the values of its aesthetic parameters, such as area, width, expansion, maximal and total edge length, or non-planarity. However, in this general framework and from an algorithmic point of view, optimal embeddings or equivalently nice drawings of graphs are intractable. In general, they are NP-complete, which means that one must pay for nice drawings with a high computational effort. This fact holds even for trees. To the contrary, there are drawings of trees which satisfy the upper and lower bounds up to some constant factor and are computable in polynomial time Bibtype: Article Author: F. J. Brandenburg Pages: 1-15 Month: may Source: Visualization in Human-Computer Interaction Title: Nice drawings of graphs are computationally hard Year: 1988 Keyword: computational complexity, computational geometry, graph theory, trees (mathematics), computationally hard, formal approach, graph embedding, guest graph, host graph, descriptive capabilities, real applications, optimizations, niceness, aesthetic parameters, area, width, expansion, edge length, non-planarity, optimal embeddings, equivalently nice drawings, NP-complete, computational effort, trees