|
Straight Line Grid Embeddings Via Normal
Labelings |
Original Graph #0
 |
Original Graph #4
 |
Planar Graph #0
 |
Planar Graph #4
 |
Conversion from the original graph to the
planar representation was done using Lincoln Lu's graph drawing
program. This was accomplished by first drawing the original graph in
the applet and then moving the vertices around until there were no edge
crossings.
|
|
Triangulated Planar Graphs
|
Triangulated Planar Graph #0
 |
Triangulated Planar Graph #4
 |
| In order to triangulate the original planar
graphs, edges had to be added. This was accomplished by adding edges
between vertices until each face had three edges. Added edges are shown in
red. |
|
|
Triangulated Planar Graphs with Labeled Angles
|
Triangulated Planar Graph #0 w/ Angles
 |
Triangulated Planar Graph #4 w/ Angles
 |
The graphs and their corresponding labels
were made with the following 3 properties:
- The outer 3
vertices of the graph have the same number for all of their angles.
-
The angles in each triangle in the graph are assigned counterclockwise
with the labels 1, 2, and 3.
- For the interior vertices when traveling
around an interior vertex, the 1's, 2's and 3's must be in consecutive
order.
|
|
Triangulated Planar Graphs with Colored Trees
|
Triangulated Planar Graph #0 w/ Colored
Trees
 |
Triangulated Planar Graph #4 w/ Colored
Trees
 |
A color was chosen for each angle number. Each
edge will have an end which contains two of the same number. The color
corresponding to the number in which the edge had duplicate numbers on one
of its ends was used to color that edge.
|
|
Calculations made to draw straight line embedding
|
| Graph #0
Calculations |
| Vertex |
x |
y |
z |
| 1 |
4 |
3 |
6 |
| 2 |
- |
- |
- |
| 3 |
- |
- |
- |
| 4 |
5 |
1 |
7 |
| 5 |
1 |
4 |
8 |
| 6 |
- |
- |
- |
| 7 |
8 |
4 |
1 |
| 8 |
3 |
8 |
2 |
| 9 |
2 |
7 |
4 | |
| Graph #4
Calculations |
| Vertex |
x |
y |
z |
| 1 |
10 |
1 |
2 |
| 2 |
2 |
4 |
7 |
| 3 |
- |
- |
- |
| 4 |
1 |
2 |
10 |
| 5 |
3 |
6 |
4 |
| 6 |
5 |
3 |
5 |
| 7 |
- |
- |
- |
| 8 |
- |
- |
- |
| 9 |
4 |
8 |
1 | |
Each vertex has a single unique path, one of each color,
that starts at the vertex and travels to an outer vertex. The result of
these paths are 3 distinct regions which can be seen as the upper left,
upper right, and bottom. The number of faces in the upper left region is
x, in the lower region is y, and the upper right region is z. |
|
Straight Line Embeddings
|
Triangulated Planar Graph #0 w/ Colored
Trees
 |
Triangulated Planar Graph #4 w/ Colored
Trees
 |
Each vertex was placed in the straight line
embedding according to the calculations made above. Then edges were added
between each vertex as they were in the original graph.
|
*All images drawn using Photoshop 6.0
|