Drawing graphs in the plane with high resolution
Drawing graphs in the plane with high resolution
复制标题
在平面上以高分辨率绘制图形
DOI：
10.1109/fscs.1990.89527
复制
发表时间：
1990
期刊：
影响因子：
--
通讯作者：
G. Woeginger
中科院分区：
文献类型：
--
作者：
Michael Formann;T. Hagerup;J. Haralambides;Michael Kaufmann;F. Leighton;A. Symvonis;E. Welzl;G. Woeginger
研究了在平面上画一个图，使其边为直线，且任意一对相交边所成的最小夹角最大的问题。布局的分辨率被定义为图形的入射边形成的最小角度的大小，并且图形的分辨率被定义为图形的任何布局的最大分辨率。用图的最大结点度d来刻画图的可分解度R，证明了对任意图，Ω（1/d/sup 2/）≤ R ≤ 2 pi /d.此外，还证明了许多图的R= Theta（1/d），包括平面图、完全图、超立方体、多维网格和环面以及其他特殊网络。还证明了当d=4时，判定图的R=2 pi /d的问题是NP-难的，并利用一个计数参数证明了许多图的R=O（log d/d/sup 2/）. <<ETX>>
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.<<ETX>>