Browse Prior Art Database

A technique for horizontal coordinate assignment in a directed graph layout

IP.com Disclosure Number: IPCOM000132000D
Original Publication Date: 2005-Nov-28
Included in the Prior Art Database: 2005-Nov-28
Document File: 4 page(s) / 75K

IBM

Abstract

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 et.al., 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.

1

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

2