CS 5764: Information Visualization

Homework #5:  Graph Drawing

The purpose of this assignment is to give you an appreciation of how challenging it is to lay out a graph in the plane.

Instructions:

Below is an adjacency matrix for an undirected graph. Your objective is to design an aesthetically pleasing graph drawing of it.  This will require you to generate a positioning for all the vertices on a 2D surface, and perhaps other visual representation issues.  Please draw the graph using a node-link technique: vertices are represented by nodes with the vertex number inside. Edges are represented by lines between vertices. You MUST draw the graph manually; you may NOT use an automatic graph visualization tool.

Hand in:  (in class)

You should turn in two pages:

 

      1   2   3   4   5   6   7   8   9   10
     ---------------------------------------
    |
  1 | 0   0   1   0   0   1   1   0   0   0
    |
  2 | 0   0   1   0   0   1   0   1   1   0
    |
  3 | 1   1   0   0   0   0   0   0   0   1
    |
  4 | 0   0   0   0   1   0   1   0   1   0
    |
  5 | 0   0   0   1   0   0   0   1   0   0
    |
  6 | 1   1   0   0   0   0   0   0   1   1
    |
  7 | 1   0   0   1   0   0   0   1   0   0
    |
  8 | 0   1   0   0   1   0   1   0   0   0
    |
  9 | 0   1   0   1   0   1   0   0   0   0
    |
 10 | 0   0   1   0   0   1   0   0   0   0
    |

(This assignment adapted from John Stasko.)