EDGE CROSSINGS IN DRAWINGS OF BIPARTITE GRAPHS

被引：160

作者：

EADES, P ^{[1
]}

WORMALD, NC ^{[1
]}

机构：

[1] UNIV MELBOURNE, DEPT MATH, PARKVILLE, VIC 3052, AUSTRALIA

来源：

ALGORITHMICA | 1994年 / 11卷 / 04期

关键词：

GRAPH; BIPARTITE GRAPH; DIRECTED GRAPH; EDGE CROSSING; MEDIAN;

D O I：

10.1007/BF01187020

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

Systems engineers have recently shown interest in algorithms for drawing directed graphs so that they are easy to understand and remember. Each of the commonly used methods has a step which aims to adjust the drawing to decrease the number of arc crossings. We show that the most popular strategy involves an NP-complete problem regarding the minimization of the number of arcs in crossings in a bipartite graph. The performance of the commonly employed ''barycenter'' heuristic for this problem is analyzed. An alternative method, the ''median'' heuristic, is proposed and analyzed. The new method is shown to compare favorably with the old in terms of performance guarantees. As a bonus, we show that the median heuristic performs well with regard to the total length of the arcs in the drawing.

引用

页码：379 / 403

页数：25