发明名称 |
Technique for drawing directed graphs |
摘要 |
The present invention relates to a computer-implemented technique for drawing directed graphs providing reduced crossings and improved picture quality. An edge list description provided by a user is processed to produce a ranking of all nodes that minimizes the weighted sum of all edges, an edge cost being the product of its weight and length. Nodes within a ranking are then positioned to reduce edge crossings using a heuristic based on node positions in adjacent ranks. Such heuristic uses a generalized median as a weighting function plus node transposition to avoid senseless edge crossings before proceeding to a next rank. Nodes are then positioned to minimize the weighted sum of horizontal distances among connected nodes. Spline control points are then computed for interconnected nodes, and a code sequence for a drawing is generated.
|
申请公布号 |
US4953106(A) |
申请公布日期 |
1990.08.28 |
申请号 |
US19890355731 |
申请日期 |
1989.05.23 |
申请人 |
AT&T BELL LABORATORIES |
发明人 |
GANSNER, EMDEN R.;NORTH, STEPHEN C.;VO, KIEM-PHONG |
分类号 |
G06T11/20 |
主分类号 |
G06T11/20 |
代理机构 |
|
代理人 |
|
主权项 |
|
地址 |
|