Screenshots and Examples of ULP Trees
The screenshots on this page are based upon the figures from the journal version of the ULP tree paper.
For each screenshot, a GraphSET file is provided that can be directly manipulated to better understand the ULP tree drawing and recognition algorithms.
To alter the track number of a vertex, first select the option "Automatically Update Track Numbers" under the "Grid and Tracks" menu. Then as the vertices are moved between tracks, the track number of the vertex will be updated accordingly. Next, make sure that the rightmost "Lock to tracks" toolbar button is not selected. Otherwise, the vertex can only be moved right and left and not up and down between tracks.
After altering the track numbers, select the option "Draw ULP Trees" under the "Algorithms" menu option. If animate option is selected from the popup dialog, the tree will drawn incrementally to better illustrate the algorithm.
ULP Trees with Distinct Labels
The following screenshots are for trees that ULP provided each vertex has a distinct label, i.e., each track has only one vertex.
When altering track numbers for trees in this section, please verify that each track has at most one vertex before attempting to redraw the tree using the provided algorithm. Otherwise, the tree will not be redrawn without crossings.
Figure 2 - Caterpillar on 30 Levels
A caterpillar is tree in which only a path remains after removing all leaves.
Figure 2 GraphSET file: |
 |
Figure 3 - Radius-2 Star on 29 Levels
A radius-2 star is a subtree of a double star in which at least one leaf is a distance 2 from the root vertex.
Figure 3 GraphSET file: |
|
Figure 7 - Degree-3 Spider on 20 Levels
A degree-3 spider consists of three paths with one endpoint in common.
For this example and the next, bends are used since otherwise exponential area would be required. Bends are automatically added once the tree is drawn. These can be removed with "Remove All Edge Bends" option under the "Graph" menu.
Figure 7 GraphSET file: |
|
Please note unlike the previous two examples, the vertices for this tree and the next have numeric labels explicitly provided in the figures in the paper. This might lead to confusion in GraphSET since its tracks are numbered from top to bottom, whereas, in the paper, levels are numbered from the bottom to the top.
To handle this discrepancy, GraphSET provides the ability for a vertex to have a name that is independent of its track number. For this figure and the next, the vertices are named according to the numeric label given in the paper. The vertex track numbers are set so that the final drawing will match that in the paper.
Please also note that vertices names do not change as the vertex is repositioned (if the "Automatically Update Track Number" option is set). To see track numbers instead, select the "Show Vertex Track Number" option under the "Graph" menu.
Figure 8 - Degree-3 Spider Worst Case
The following is a worst case degree-3 spider in that it requires the most area if drawn with straight-line edges if bends are not used.
Figure 8 GraphSET file: |
|
ULP Trees with Duplicate Labels
The following screenshots are for trees that ULP even when are duplicate labels are permitted. Here each track can have multiple vertices so long as no pair of adjacent vertices are the same track.
When altering track numbers for the tree in this section, please verify that all edges have endpoints on distinct tracks before attempting to redraw the tree. Otherwise, the tree will not be redrawn without crossings.
Figure 11 - Caterpillar on 8 Levels
A caterpillar is the only tree which is always ULP with duplicate labels.
Figure 11 GraphSET file: |
|