Improved approximations of crossings in graph drawings
Improved approximations of crossings in graph drawings
复制标题
改进图形绘制中交叉点的近似值
DOI：
10.1145/335305.335340
复制
发表时间：
2000
期刊：
影响因子：
--
通讯作者：
B. Schieber
中科院分区：
文献类型：
--
作者：
G. Even;S. Guha;B. Schieber
我们对两个经典的嵌入问题给出了改进的近似：（i）在平面上绘制有界度图时最小化交叉数;（ii）最小化四度图的VLSI布局面积。这些改进的算法可以应用于改善各种VLSI布局问题。我们的结果如下。(i)我们计算一个有界度图的平面上的绘图，其中顶点和交叉点的数目之和是O（log an）倍的最佳最小和。这是相对于最佳已知结果的对数因子改进。(ii)我们计算了一个VLSI布局的度四图在一个网格具有恒定的纵横比，其面积是O（log 4 nI倍的最佳最小布局面积。这是一个O（log 2 n）的改进，最好的已知长期的结果。
We give improved approximations for two classical embedcling problems: (i) minimizing the number of crossings in a drawing of a bounded degree graph on the plane; and (ii) minimizing the VLSI layout area of a degree four graph. These improved algorithms can be applied to improve a variety of VLSI layout problems. Our results are as follows. (i) We compute a drawing on the plane of a bounded degree graph in which the sum of the numbers of vertices and crossings is O(log a n) times the optimal minimum sum. This is a logarithmic factor improvement relative to the best known result. (ii) We compute a VLSI layout of a degree four graph in a grid with constant aspect ratio the area of which is O(log 4 n I times the optimal minimum layout area. This is an O(log 2 n) improvement over the best known long standing result.