Graph Drawing Contest 1998

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

Last change: 31. August 1998

Data and rules

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

How layouts of graphs were obtained

All work was done using our program package Pajek.
  1. Graph A
    The data for graph A consist of addition and deletion operations that specify how the graph changes over time. In our solution addition and deletion operations were performed using macro language which is recognized by program package Pajek. Then we used Microsoft Camcorder (free software) to record the process. Some pictures on paper in three different time points are shown.
  2. Graph B
    Symmetries in graph (with some exceptions) can easily be noticed. We started the drawing using the layout obtained by Fruchterman-Reingold spring embedder. Later we used manual editing to maximize symmetries and made some displacements according to different sizes and shapes of nodes. Pajek was used to do all the work.
  3. Graph C
    Using spring embedders we could not get any nice layouts. Analysing graph we found that it is a symmetric cubic graph. Later we used eigenvectors approach and computed eigenvectors of neighbourhood matrix that correspond to the largest eigenvalue (which is multiple). In this way we got nice symmetric picture in space (3D). According to symmetries (equivalences) some of the nodes are drawn on the same positions and some are overlapping when selecting the certain view to see the symmetries. Since some vertices are overlapping we built a list of overlapping vertices drawn in different colors: Group Color Vertices ---------------------------------------------------- 1. Yellow 13, 76 2. Green 9, 12, 33,106 3. Pink 39, 65, 88,112 4. Blue 5, 20, 51, 63 5. Fuchsia 68, 75, 85, 92 6. White 36, 99 7. Orange 21, 42 8. Purple 23, 24, 55, 89 9. NavyBlue 30, 44, 54, 57 10. TealBlue 3, 11, 43,101 11. OliveGreen 1, 18, 64, 74, 91,103,104,107 12. Gray 19, 26, 47, 59 13. Black 17, 40, 70, 79 14. Maroon 48, 53 15. LightGreen 25, 32, 35, 60, 66, 71, 73,105 16. Cyan 10,102 17. Yellow 2, 22, 81, 90 18. Green 14, 58, 61, 83 19. Pink 4, 15, 46, 52, 77, 78,109,110 20. Blue 7, 8, 27, 41 21. Fuchsia 6, 50, 67, 96 22. White 82, 84, 95, 97 23. Orange 31, 80 24. Purple 16, 29, 98,108 25. NavyBlue 38, 72, 86, 87 26. TealBlue 37, 45 27. OliveGreen 28, 62, 93,111 28. Gray 34, 49, 56,100 29. Black 69, 94 ----------------------------------------------------
  4. Graph D
    Large graph can be generated from words in a dictionary. We constructed a graph in which two words are connected iff one can be obtained from the other by changing single character (e. g. WORK-WORD) or by adding/deleting one character (e.g. EVER-FEVER). Then we took english words graph-drawing-contest, find all shortest paths between graph and drawing and between drawing and contest, draw the obtained graph using layers option in Pajek (layers are determined by distance from drawing). Additionally we added two puzzles:
    • one difficult: find shortest paths alone,
    • one easy: find only missing words on the paths.

Drawings

Results

Authors:
Vladimir Batagelj, Department of Mathematics, University of Ljubljana
e-mail: vladimir.batagelj@uni-lj.si
Andrej Mrvar, Faculty of Social Sciences, University of Ljubljana
e-mail: andrej.mrvar@uni-lj.si