Graph Drawing Contest 1997

Layouts by
Vladimir Batagelj and Andrej Mrvar
University of Ljubljana, Slovenia

Last change: 1. October 1997

Data and rules

How layouts of graphs were obtained

1. Graph A
   • Automatically obtained layout using draw/eigenvalues option in program Pajek. Manual editing to reposition vertices in the grid to obtain orthogonal layout in plane.
   • Manual editing in 3D to get orthogonal embeddings in space: minimal, symmetric and cube.
2. Graph B
   • Analyzing graph B using our program MODEL we obtained (almost) regular partition in 3 classes. The third class contains only vertex Harmony Central. The second class, represented by squares, contains 11 vertices that are connected only to the vertices in the class 1 (represented by circles). Vertices in class 1 are also connected to other vertices in the same class. We first draw all vertices in the class 1 in the center and vertices in class 2 separately -- using class shrinking and circular drawing options in Pajek. Afterward we manually moved vertices of class 1 connected to only one vertex of class 2 close to this vertex. Finally we manually arranged the remaining vertices of class 1.
   • We transformed given similarities s on arcs to dissimilarities d = 1 /(1 + s) and applied Ward's hierarchical clustering method to the obtained dissimilarity matrix. We produced a clustering into 12 clusters, shrank the graph using Pajek, and draw the obtained skeleton minimizing the number of crossings. Finally we manually arranged the vertices of original graph.

See also our Graph drawing report PS/ZIP or PDF.

Drawings

• Graph A:
  Graph A - layout in plane (EPS); Graph A - minimal 1 (GIF); Graph A - minimal 2 (GIF); Graph A - minimal (VRML);
  Graph A - symmetric (GIF); Graph A - symmetric (VRML);
  Graph A - cube 1 (GIF); Graph A - cube 2 (GIF); Graph A - cube (VRML);
• Graph B:
  Graph B - regular (EPS); Graph B - dendrogram (PS); Graph B - clustering (EPS);

Results

• Message; Report from organizers.

Authors: