Drawing graphs in the plane with high resolution

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 Ω(1/d²)⩽R⩽2π/d for any graph. Moreover, it is proved that R=Θ(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π/d for a graph is NP-hard for d=4, and a counting argument is used to show that R=O(log d /d²) for many graphs