DRAWING GRAPHS IN THE PLANE WITH HIGH-RESOLUTION

This paper presents the problem of drawing a graph in the plane so tha t edges appear as straight lines and the minimum angle formed by any p air of incident edges is maximized. The resolution of a layout is defi ned to be the size of the minimum angle formed by incident edges of th e graph, and the resolution of a graph 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 OM EGA(1/d2) less-than-or-equal-to R less-than-or-equal-to 2pi/d for any graph. Moreover, it is proved that R = THETA(1/d) for many graphs incl uding planar graphs, complete graphs, hypercubes, multidimensional mes hes and tori, and other special networks. It is also shown that the pr oblem of deciding if R = 2pi/d for a graph is NP-hard for d = 4, and b y using a counting argument that R = O(log d/d2) for many graphs.