Lade Daten...
iLearn
Cau-siegel-color-300

Automatic Graph Drawing

Moduldatenbank, UnivIS

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 class 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, ELK is now an official Eclipse project.

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

Resources

We will provide you with different kinds of resources over the course of this... well, course.

Literature

  • Roberto Tamassia, Editor, Handbook of Graph Drawing and Visualization, CRC Press, 2013; especially chapters 1, 2, 5, 12, 13, 15. Online version available here!
  • Ioannis Tollis, Peter Eades, Giuseppe Di Battista, Roberto Tamassia, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1998.

Lecture Slides

  1. Modeling Pragmatics pdf (last update: April 13)
  2. Terminology pdf (last update: July 25)
  3. Force-Directed Drawing pdf (last update: May 4)
  4. Stress pdf (last update: May 10)
  5. Layer-Based Drawing pdf (last update: May 25)
  6. Ports and Hyperedges pdf (last update: May 18)
  7. Nodes and Their Size pdf (last update: May 25)
  8. Trees pdf (last update: June 22)
  9. Evolving Trees (guest lecture by Malte Skambath) pdf, animated version, may not work with Firefox (last update: July 7)
  10. Planarity and Orthogonal Drawings pdf (last update: July 6)
  11. Labels (...und was Herrn Schulze sonst noch so einfällt) pdf, pdf (with notes that help you figure out what the slides are actually supposed to mean) (last update: July 12)

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.

Exam

Prerequisites: You must have received at least 50% of homework assignment points to be allowed to take the exam.

Date: Wednesday, July 20th, 12:00 to 14:00, CAP 2 Room B.

Results: Monday, July 25th, 10:00 to 10:30, CAP 4 Room 1110.

Grade: You need at least 50% of exam points to pass the exam. If that is the case, your grade is calculated as follows:

\[\min\left( \text{final exam}, 85\% \text{ final exam } + 15\% \text{ homework} \right)\]

In borderline cases, we may also choose to consider your participation in class.