Patent ID: 7363583
Filing Date: 2008-04-22
Classification: G06Q

Abstract:
1. A computer-implemented method for providing a compact layout of connected nodes, comprising: searching for a deepest non-leaf node along an unsearched path of edges from a root node of a hierarchical configuration of connected nodes, wherein the configuration includes an edge between each pair of connected nodes; when a deepest non-leaf node is found along the unsearched path, positioning all descendant nodes of the deepest non-leaf node into a first compact layout of connected nodes, wherein the difference between the width and the height of the first compact layout is minimized; determining whether the deepest non-leaf node has a non-leaf sibling node; when the deepest non-leaf node has a non-leaf sibling node, positioning all descendant nodes of the non-leaf sibling node of the deepest non-leaf node into a second compact layout of connected nodes, wherein the difference between the width and the height of the second compact layout is minimized; determining whether a parent node of the deepest non-leaf node is the root node; when the parent node of the deepest non-leaf node is not the root node, positioning all descendant nodes of the parent node of the deepest non-leaf node, including a sub-tree resulting from the positioning all descendant nodes of the deepest non-leaf node, into a third compact layout of connected nodes, wherein the difference between the width and the height of the third compact layout is minimized; repeating, for each path of edges from the root node, the foregoing steps of (a) searching for a deepest non-leaf node, (b) positioning all descendant nodes of the deepest non-leaf node, (c) positioning all descendant nodes of a non-leaf sibling node, and (d) positioning all descendant nodes of a parent node; positioning all descendant nodes of the root node, including all child sub-trees of the root node resulting from the repeating, into a fourth compact layout of connected nodes, wherein the difference between the width and the height of the fourth compact layout is minimized; and rendering the positioned nodes of the fourth compact layout on an output devices wherein rendering includes depicting each of the positioned nodes and the edge between each pair of connected nodes.