iLearn

What is this?

Graphs are found in numerous areas of computer science and beyond. For example, software engineers make regular use of class diagrams, automata or flow charts. Hardware design makes use of net lists and circuit diagrams. The drawing of a graph is its visual representation. The manual creation of a well-readable drawing, such as the design of a UML diagram with a software engineering tool, can be a very time consuming activity.

This class covers approaches for the efficient, automatic creation of well-readable diagrams. This is an application-driven form of algorithm engineering, where cognitive psychology plays an important role. Graph drawing methods are used increasingly for example in “auto-layout” features of development tools.

The lecture stretches from theoretical foundations to practical implementations. We here make use of the Eclipse-based open source tool KIELER (Kiel Integrated Environment for Layout) and the Eclipse Layout Kernel (ELK). Both of these projects are developed at the RTSYS research group.

What you will learn in this course:

• Foundations of graph theory
• Aesthetics criteria
• Tooling, usage of ELK and KIELER
• Drawing trees
• Force-based drawing
• Hierarchical graph drawing
• Planarization-based graph drawing
• Labeling approaches

Homework Assignments

You will work on your assignments in teams of two. Homework assignments can range from theoretical assignments to actually implementing layout algorithms yourselves (which is, in fact, pretty cool). Depending on the concrete set of assignments, you will have either one or two weeks to work on them.

For the practical assignments, you will need an Eclipse development environment. You will work with certain technologies developed at our group to implement layout algorithms. We will post more details as well as give you an overview of the technologies once we’ve got everything sorted out properly.

Please Note: Not all of the technologies are documented as well as they should be. We will try and take this course as an incentive to change that. However, whenever you find some piece of documentation unclear or even missing, tell us about it and we’ll go find someone to fix that. The same goes for bugs in software.

Resources

Lecture Slides

1. Lecture 1: Modeling Pragmatics pdf (last update: 2019-11-01)
2. Lecture 2: Terminology pptx (last update: 2019-11-01)
3. Lecture 3: Force-Directed Drawing pptx (last update: 2019-11-01)
4. Lecture 4: Stress pptx (last update: 2019-11-01)
5. Lecture 5: Layer-Based Drawing pptx (last update: 2019-11-01)
6. Lecture 6: Ports and Hyperedges pptx (last update: 2019-09-09)
7. Lecture 7: Nodes and Their Size pptx (last update: 2019-09-09)
8. Lecture 8: Trees pptx (last update: 2019-09-09)
9. Lecture 9: Serial-Parallel Digraphs pptx (last update: 2019-09-09)
10. Lecture 10: Labels pptx (last update: 2019-09-09)
11. Lecture 11: Planarity pptx (last update: 2019-09-09)
12. Lecture 12: Topology-Shape-Metrix (guest lecture by Petra Mutzel) pdf (last update: 2019-09-09)
13. Lecture 13: Planar Orientations pptx (last update: 2019-09-09)
14. Lecture 14: Introduction to HCI: David Joyner’s class “CS 6750: Human-Computer Interaction” at Georgia Tech (for link to videos, go to “Current Semester” -> “Full Calendar”) (last update: 2019-09-09)

Notes:

• These slides are initialized with those from the last edition of this class. They will evolve over time.
• I’m happy to share the slides, and some of them have originally been created and kindly shared by other colleagues before, as acknowledged in the slides. To facilitate further editing, I generally provide the .pptx sources, unless they get beyond 10MB or so or .pptx is not available. If you do use these slides, feel free to drop me a note (rvh@informatik.uni-kiel.de), in particular if you have suggestions for improvements/extensions.

Literature

• Roberto Tamassia, Editor, Handbook of Graph Drawing and Visualization, CRC Press, 2013; insbesondere Kapitel 1, 2, 5, 12, 13, 15. On-line verfügbar unter http://cs.brown.edu/people/rtamassi/gdhandbook/
• Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis Tollis, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

Layout Algorithm Development

Installing Eclipse

You need to install Eclipse to develop layout algorithms for ELK. Follow the following followable steps to do so:

1. Make sure you have Java installed (at least version 1.8).
3. After having started the installer, switch into Advanced Mode by clicking the Hamburger icon in the top right corner.
4. Choose the Eclipse IDE for Java Developers and click Next.
5. Click the plus icon at the top right corner and enter the following resource URI: https://git.rtsys.informatik.uni-kiel.de/projects/KIELER/repos/config/raw/setups/GraphDrawing.setup
6. Select the Graph Drawing setup that just appeared in the list and click Next.
7. Adjust the preferences to taste and click Next.
8. Ignore the information and hit the Finish button.

After a while, your brand new Eclipse installation will open and configure itself to be used for layout algorithm development. Using your algorithms requires starting a new Eclipse instance from your IDE (Eclipse-ception), which entails creating a new run configuration:

1. From the Run menu, choose Debug Configurations.
2. Add a new Eclipse Application and choose a proper name.
3. Hit Apply and Debug to start the new application.
4. Once it has opened, you will want to open a few views that will help you develop and debug your algorithms. From the Window -> Show View -> Other dialog, open the following views:
• Layout, Layout Graph, and Layout Time from the Eclipse Diagram Layout category.
• Diagram from the KIELER Lightweight Diagrams category (not Diagram (Deprecated); it’s deprecated for a reason).
5. Open the preferences and activate the Execution time measurement option on the Eclipse Diagram Layout page.

To test your layout algorithms (or verify whether things work after the installation), do this:

1. In the Eclipse instance you started from the other Eclipse instance, create a new project.
2. In that new project, create a new file with the .elkt extension.
3. Paste the following:
node n1
node n2
edge n1 -> n2

1. The Diagrams view should display a simple graph.

Creating an Algorithm Project

To create a first algorithm, simply follow this guide and create a plug-in project on the ELK website.

Documentation

The ELK website has general documentation as well as a reference of all layout algorithms and options built into ELK. This will be your main source of documentation. If you’re missing anything or if things are not understandable, please tell us so we can fix it.