Visualization of Trees Embedded in Undilated Hypercubes

Project Proposal for Information Visualization
Computer Science 533C
Spring 2003
Instructor: Tamara Munzner


James Slack
jslack@cs.ubc.ca

February 12, 2003

  1. Abstract

    A reason why people care about embedding trees in hypercubes has roots in parallel multiprocessor systems. A traditional multiprocessor system is engineered to represent a hypercube but many problems associated with parallel system processing depends on algorithms that resemble binary decision trees. The importance of finding embeddings of trees in hypercubes is relevant, but it is very difficult to visualize such embeddings when the dimensionality of systems being analyzed is more than 3. I propose to reduce the effort required to understand the topology of specified trees in hypercubes with up to 6 dimensions. My project will focus on visualization of single trees embedded in a hypercube as well as comparing two embedded trees for similarly embedded regions.

  2. Introduction

    The two structures being used in for this project are binary trees and hypercubes. Each of these structures will be explained in minor detail to motivate the visualization.

    1. Strongly Balanced Trees

      A set of binary trees that I may use are called strongly balanced, which by definition means that the trees can be constructed by adding connected pairs of nodes to an existing strongly balanced tree. This structure is hypothesized to be always embeddable in k-dimensional undilated hypercube when trees with 2k nodes are constructed. An undilated hypercube is simply a hypercube that has edges and nodes of single capacity; only one edge of an embedded tree can be assigned to a hypercube edge and hypercube nodes may only be used once by a single tree node. The 32-node binary tree in Figure 1 is embeddable in a 5-dimensional hypercube; the colours will be explained in the next section.


      Figure 1: A strongly balanced binary tree

      These trees have been generated (not embedded in a hypercube) by Markus Aderhold, in CPSC 521 (Parallel Algorithms) and will also be used by Markus and I in CPSC 533C (Stochastic Search Algorithms) this term as we attempt to embed the trees using a variety of stochastic methods.

    2. Embedding Trees in Hypercubes

      Embedding trees in hypercubes is a hard combinatorial problem. In CPSC 533C, Markus and I will embed trees in hypercubes but will lack visualization tools to show interesting views of the hypercube structure. Viewing the outcome of our embeddings will be extremely helpful in determining interesting results from our stochastic approach. Viewing partially computed results and comparing results from successful encodings may allow us to visually determine how to improve our algorithms. Figure 2 is the above 32-node binary tree from Figure 1 embedded (by hand) in a hypercube.

      Figure 2: A hypercube with binary tree embedded

      Since the number of nodes is much smaller than the number of edges (32 nodes, 80 edges in a 5 dimensional hypercube), hypercubes of more than 3 dimensions can be displayed in 3 dimensional space. The limitations of this approach may be 6 dimensions (64 nodes, 192 edges) and will require a graphics package capable of some desirable transformations.

  3. Visualizing Embedded Trees

    The first half of my implementation will consist of being able to visualize a tree and the associated hypercube. I will attempt to create an interface which allows for the selection of individual nodes and edges of either component. The hypercube component will require interaction, perhaps in 5 and 6 dimensions some of the edges will be occluded. This shouldn't be too much of a problem given the sparse nature of the trees, but I could also add a randomization process to mix up the direction of each dimension. Some more experimenting will need to be done to find a good solution to this. The tree component will either remain static or perhaps I will make it unrooted. This might make it more confusing, but it might also make the tree layout more meaningful in sections if the user wishes to rebalance the tree by interactively selecting the root to concentrate on a particular segment.

  4. Comparing Two Embedded Trees

    5. The second half of my implementation involves using the interface from the first half and linking a second tree interactively with the first one. The interfaces will need to show how two segments of the embedding are similar, so an interface to change the dimensional layout of a hypercube while retaining the embedding will be required. I'll need to experiment with randomization and selection procedures since there are k! different dimensional layout choices for a k-dimensional hypercube (each embedded dimension may be assigned to a layout dimension. Getting two laid out hypercubes to look most similar is the goal, it might be easier to tweak once the user can make reference with a uninformed random start).

  5. Implementation Approach

    I am thinking about using geomview for the visualization of both hypercubes and trees, and perhaps attaching a Java interface to communicate with the geomview API, simply because I'm more familiar with Java and it should be rather simple to come up with a decent interface quickly so I can concentrate on the visualization details first, then make the interface usable.