Confluent layered drawings

被引：23

作者：

Eppstein, David ^{[1
]}

Goodrich, Michael T. ^{[1
]}

Meng, Jeremy Yu ^{[1
]}

机构：

[1] Univ Calif Irvine, Sch Informat & Comp Sci, Irvine, CA 92697 USA

来源：

ALGORITHMICA | 2007年 / 47卷 / 04期

关键词：

graph drawing; confluent drawing; layered drawing; cross reduction;

D O I：

10.1007/s00453-006-0159-8

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

We combine the idea of confluent drawings with Sugiyama-style drawings in order to reduce the edge crossings in the resultant drawings. Furthermore, it is easier to understand the structures of graphs from the mixed-style drawings. The basic idea is to cover a layered graph by complete bipartite subgraphs (bicliques), then replace bicliques with tree-like structures. The biclique cover problem is reduced to a special edge-coloring problem and solved by heuristic coloring algorithms. Our method can be extended to obtain multi-depth confluent layered drawings.

引用

页码：439 / 452

页数：14

共 29 条

[1]

BARTH W, 2003, LECT NOTES COMPUTER, V2528, P130

[2] NEW METHODS TO COLOR THE VERTICES OF A GRAPH [J].

BRELAZ, D .

COMMUNICATIONS OF THE ACM, 1979, 22 (04) :251-256

[3]

Campers G., 1988, Operational Research '87. Proceedings of the Eleventh International Conference, P917

[4] AUTOMATIC DISPLAY OF HIERARCHIZED GRAPHS FOR COMPUTER-AIDED DECISION-ANALYSIS [J].

CARPANO, MJ .

IEEE TRANSACTIONS ON SYSTEMS MAN AND CYBERNETICS, 1980, 10 (11) :705-715

[5]

Dickerson M, 2004, LECT NOTES COMPUT SC, V2912, P1

[6]

Eades P., 1990, Journal of Information Processing, V13, P424

[7]

ELLSON J, GRAPHVIZ

[8]

ESCHBACH T, 2003, LECT NOTES COMPUTER, V2528, P285

[9] Bipartite dimensions and bipartite degrees of graphs [J].

Fishburn, PC ;

Hammer, PL .

DISCRETE MATHEMATICS, 1996, 160 (1-3) :127-148

[10]

FORSTER M, 2003, LECT NOTES COMPUTER, V2528, P276

← 1 2 3 →