Category: GraphLayout
Organization: F.T.; Simvonis, A.; Welzl, E.; Woeginger, G.
        Fachbereich Math., Freie University Berlin, West
        Germany
Abstract: The problem of drawing a graph in the plane so that
        edges appear as straight lines and the minimum angle
        formed by any pair of incident edges is maximized is
        studied. The resolution of a layout is defined to be
        the size of the minimum angle formed by incident
        edges of the graph, and the resolution of a graph is
        defined to be the maximum resolution of any layout
        of the graph. The resolution R of a graph is
        characterized in terms of the maximum node degree d
        of the graph by proving that Omega (1/d/sup
        2/)<or=R<or=2 pi /d for any graph. Moreover, it is
        proved that R= Theta (1/d) for many graphs,
        including planar graphs, complete graphs,
        hypercubes, multidimensional meshes and tori, and
        other special networks. It is also shown that the
        problem of deciding if R=2 pi /d for a graph is
        NP-hard for d=4, and a counting argument is used to
        show that R=O(log d/d/sup 2/) for many graphs
Number: 90
Bibtype: InProceedings
Booktitle: Proceedings of 31st Annual Symposium on Foundations
        of Computer Science
Author: M. Formann
        T. Hagerup
        J. Haralambides
        M.
        Kaufmann
        M. Kaufmann
Pages: 86-95
Month: oct
Title: Drawing graphs in the plane with high resolution
Year: 1990
Volume: 1
Keyword: graph theory, optimisation, high resolution planar
        graph drawing, straight line edges, NP-hard problem,
        minimum angle, incident edges, maximum node degree,
        complete graphs, hypercubes, multidimensional
        meshes, tori, counting