Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A Technique For Determining Horizontal Placement of Nodes in a Compound Directed Graph Drawing

IP.com Disclosure Number: IPCOM000028494D
Original Publication Date: 2004-May-17
Included in the Prior Art Database: 2004-May-17
Document File: 3 page(s) / 69K

Publishing Venue

IBM

Abstract

Compound directed graphs appear in various types of tools. For example, a business process diagram (or "flow" diagram) may depict a bunch of activities connected with edges. Activities may be nested inside other "structured" activies. The structured activies are visually depicted as a box containing the nested activities. Another scenario is a class hierarchy diagram, where classes are nested inside their namespaces (e.g. java package). The problem is to determine the best placement (i.e. drawing) for the items and their containers. The process for generating a graph drawing is separated into multiple stages. The invention is regarding the final stage, which is assigining x-coordinates to nodes (assuming a top-to-bottom oriented drawing).

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 3

A Technique For Determining Horizontal Placement of Nodes in a Compound Directed Graph Drawing

GIVEN:

The compound directed graph is converted to a directed graph. The graph is given a ranking R(n), which determins the rank for each node. The nodes are ordered within each rank with an index.

ALGORITHM: From this state, an auxilary graph is generated based on the directed graph. The Network Simplex algorithm is applied to the auxilary graph to produce a minimum-cost spanning tree. This spanning tree induces the x-coordinates for the nodes. The idea of using a the network simplex algorithm to induce x-coordinates is well known and has been applied to simple directed graphs. However, in compound

directed graphs, the boundaries of subgraphs must be maintained.

Main Idea

1. Background: What is the problem solved by your invention? Describe known solutions to this problem (if any). What are the drawbacks of such known solutions, or why is an additional solution required? Cite any relevant technical documents or references. Compound directed graphs appear in various types of tools. For example, a business process diagram (or "flow" diagram) may depict a bunch of activities connected with edges. Activities may be nested inside other "structured" activies. The structured activies are visually depicted as a box containing the nested activities. Another scenario is a class hierarchy diagram, where classes are nested inside their namespaces (e.g. java package). The problem is to determine the best placement (i.e. drawing) for the items and their containers. The process for generating a graph drawing is separated into multiple stages. The invention is regarding the final stage, which is assigining x-coordinates to nodes (assuming a top-to-bottom oriented drawing).

Known solutions to the problem: http://citeseer.nj.nec.com/sander96layout.html - "Layout of Compound Directed Graphs" (1996) This solution proposes an alternative algorithm that is not as good as the proposed. Also, it does not scale as well for larger graphs.

2. Summary of Invention: Briefly describe the core idea of your invention (saving the details for questions #3 below). Describe the advantage(s) of using your invention instead of the known solutions described above.

GIVEN:

The compound directed graph is converted to a directed graph. The graph is give...