Browse Prior Art Database

A technique for horizontal coordinate assignment in a directed graph layout Disclosure Number: IPCOM000132000D
Original Publication Date: 2005-Nov-28
Included in the Prior Art Database: 2005-Nov-28
Document File: 4 page(s) / 75K

Publishing Venue



An invention for solving the horizontal placement problem when laying out a directed graph in a vertical orientation. This is the third step of a 3 step process including row assignment, crossing minimization, and final horizontal placement. Stephen North et. al. established a method for horizontal coordinate assigment in directed graph layout which uses an auxilary graph based on the original graph, and uses the Network Simplex method for establishing a spanning tree which induces an initial horitontal coordinate assignment. This initial assigment is not perfect, so it cannot be used in practice. This invention takes the initial results and refines them using an optimized data structure.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 4

A technique for horizontal coordinate assignment in a directed graph layout

Using the technique described by North, results in the following horizontal placement of nodes:

The following diagram shows the overlayed auxilary diagram, with edges that are not in the spanning tree shown in dotted lines with their associated slack values. Edges shown in bold are part of the spanning tree, and are labeled with the "cut values". So, these edges can be loosened for free, as long as the spacing requirements are not violated on the other edges.


[This page contains 1 picture or other non-text object]

Page 2 of 4

The following shows the end result of the invention:

The invention starts by taking the spanning tree and breaking it apart into clusters of nodes. This is done by first removing any edge with a value of zero from the tree, resulting in a "forest". Each tree in the forest is a Cluster. A cluster is a group of nodes which must be horizontally adjusted together to avoid increasing the cost of the resulting placement. There are still tons of original edges in the auxilary graph which were not part of the spanning tree. So, for each cluster, there are lots edges going from nodes in that cluster, to other nodes which are either in that cluster or another cluster. These edges determine the amount of forces acting on the cluster, as well as the freedom that the algorithm has to move cluster


[This page contains 2 pictures or other non-text objects]

Page 3 of 4


The following figure shows a single cluster outlined in Yellow. There are 2 edges which originate from that cluster and terminate in another. They are shown in RED. There are 3 edges which start at some other cluster, and end at the yellow cluster. Those edges are shown in blue. The Red edges define the pull toward the right, and also determine how far the cluster can be adjusted to the right. The blue edges makeup the pull to the left and define the limits to which the cluster can be adjusted in that direction.

All edges have a separation delta which nust be satisfied. If the edges connect nodes whose x coordinates are larger than that delta, then the edge has some slack in it and some imaginary amount of tension. The goal of the invention is to balance out the tension in these edges with slack, which results in coordinate assignment with certain asthetic qualities.

There are tons of edges, so one novel aspect of the invention is to reduce this amount...