A TECHNIQUE FOR DRAWING DIRECTED-GRAPHS

被引：309

作者：

GANSNER, ER

KOUTSOFIOS, E

NORTH, SC

VO, KP

机构：

[1] AT&T Bell Laboratories, Murray Hill

来源：

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING | 1993年 / 19卷 / 03期

关键词：

DIRECTED GRAPH LAYOUT ALGORITHM; NETWORK SIMPLEX;

D O I：

10.1109/32.221135

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We describe a four-pass algorithm for drawing directed graphs. The first pass finds an optimal rank assignment using a network simplex algorithm. The second pass sets the vertex order within ranks by an iterative heuristic incorporating a novel weight function and local transpositions to reduce crossings. The third pass finds optimal coordinates for nodes by constructing and ranking an auxiliary graph. The fourth pass makes splines to draw edges. The algorithm makes good drawings and runs fast.

引用

页码：214 / 230

页数：17

共 18 条

[11]

Glassner A., 1990, GRAPHICS GEMS

[12] FINDING MINIMUM-COST CIRCULATIONS BY SUCCESSIVE APPROXIMATION [J].

GOLDBERG, AV ;

TARJAN, RE .

MATHEMATICS OF OPERATIONS RESEARCH, 1990, 15 (03) :430-466

[13]

KOUTSOFIOS E, 1992, DRAWING GRAPHS DOT

[14]

ROBBINS G, SYMBOLIIKKA 87 HELSI

[15] A BROWSER FOR DIRECTED-GRAPHS [J].

ROWE, LA ;

DAVIS, M ;

MESSINGER, E ;

MEYER, C ;

SPIRAKIS, C ;

TUAN, A .

SOFTWARE-PRACTICE & EXPERIENCE, 1987, 17 (01) :61-76

[16] METHODS FOR VISUAL UNDERSTANDING OF HIERARCHICAL SYSTEM STRUCTURES [J].

SUGIYAMA, K ;

TAGAWA, S ;

TODA, M .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1981, 11 (02) :109-125

[17] A LINEAR TIME ALGORITHM FOR MINIMUM LINK PATHS INSIDE A SIMPLE POLYGON [J].

SURI, S .

COMPUTER VISION GRAPHICS AND IMAGE PROCESSING, 1986, 35 (01) :99-110

[18]

[No title captured]

← 1 2 →