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