Graph Drawing Contest 1999

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

Last change: 23. September 1999

Data and rules

See the page GD99 Graph-Drawing Contest and GD99 Graph-Drawing Conference.
See also our layouts for Graph-Drawing Contests: GD95, GD96, GD97, GD98, GD00 and GD01.

How layouts of graphs were obtained

All work was done using our program package Pajek.

  1. Graph A
    Graph data were transformed to Pajek format, which enables to handle graph changes over time. The following coding of actors is used:
    • Shapes
      • circle: =f= female
      • triangle: =m= male
      • yellow box: =b= female+male (Ernst+Lisl Wiesenhuber)
      • green box: =a= women+grandchildren (Julia von der Marwitz)
      • black diamond: =w= widowed
      • pink diamond: =d= divorced marriage
      • orange diamond: =m= still existing marriage
      • empty: =i= invisible node (white)
    • Sizes
      • 0.8 - big
      • 0.4 - small
      • 0.6 - artificial
    • Colors
      • =y= unactive characters (yellow)
      • =a= 2 persons in 2 different colors (green)
      • =b= active characters (blue)
      • =d= divorced marriage (pink)
      • =w= characters that never showed up personally (white)
      • =m= still existing marriage (orange)
      • =g= already dead characters (grey)
      • =w= widowed (black)
    • Border widths
      • =p= picture - border width = 2
      • =s= symbol - border width = 0.5
    Drawing of the current situation
    We started the drawing using the layout obtained by Kamada-Kawai spring embedder. Later we used manual editing to arrange them on rectangular net.
    Development of the graph over time
    We used the Pajek option for drawing graphs in different time points. Only time points where at least one vertex or one line changes according to last layout were drawn (e.g. 1, 2, 4, 5,...). After each change time the layout of the new graph was optimized starting with the previous positions.
  2. Graph B
    We used eigenvectors approach and computed eigenvectors of Laplacean matrix that correspond to the 1st, 2nd and 5th largest eigenvalue. No additional manual editing was used on the obtained spatial picture. Suitable view was selected to get planar EPS picture. Picture was exported to formats for the following 3D viewers: VRML (CosmoPlayer), kinemages (Mage), and MDLMOLfile (Chime).
  3. Graph C
    We started the drawing using the layout obtained by Fruchterman-Reingold spring embedder. Later we used manual editing to maximize 'rectangularity' and made some displacements to accommodate for different sizes of nodes.
  4. Graph D



Vladimir Batagelj, Department of Mathematics, University of Ljubljana
Andrej Mrvar, Faculty of Social Sciences, University of Ljubljana