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