Modulinformationssystem Informatik

 

Automatisches Zeichnen von Graphen URL PDF XML

Modulcode: Inf-GraphDraw
Englische Bezeichnung: Automatic Graph Drawing
Modulverantwortliche(r): Prof. Dr. Reinhard von Hanxleden
Turnus: unregelmäßig (SS16)
Präsenzzeiten: 2V 2Ü
ECTS: 6
Workload: 30 Std. Vorlesung, 30 Std. Präsenzübung, 120 Std. Selbststudium
Dauer: ein Semester
Modulkategorien: WI (MSc Inf (15)) WI (MSc WInf (15)) WI (MEd Inf) WPI (MEd Inf) IG (TA) (MSc Inf (2-Fach)) IS (SA) (MSc Inf (2-Fach)) IG (SA) (MSc Inf (2-Fach)) IG (MSc Inf) IS (MSc Inf) MV (MSc Inf)
Lehrsprache: Englisch
Voraussetzungen: Info

Kurzfassung:

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 tool 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.

Lernziele:

  • Properly classify different types of graphs and use correct terminology for graph aspects and properties
  • Explain basic graph analyses and their computational complexity
  • Select and apply suitably algorithmic approaches for the automatic drawing of different types of diagrams
  • Evaluate graphs concerning common aesthetics criteria

After successful completion of this module students will be able to judge for a given type of graph whether it can be drawn automatically and which algorithmic approaches are suitable. They will also be able to adapt existing drawing algorithms.

Lehrinhalte:

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

Weitere Voraussetzungen:

Mathematical foundations, as covered in Mathematik für Informatiker A und B. Alternatively, Mathematics should be a minor (Nebenfach) or second major (zweites Fach). Not required, but recommended is the participation in the modul "Graphentheorie" (Inf-GraphTheo).

Prüfungsleistung:

You need at least 50% of homework assignment points to take the final exam.

The final exam will be a layout project with presentation and documentation as specified in the homework assignments.

The final grade for the module is given by either 1) the exam grade, or 2) 85% of the exam grade + 15% of the homework grade, whichever is better of the two.

Lehr- und Lernmethoden:

Lecture, theoretical and practical exercises, reading.

Verwendbarkeit:

Literatur:

  1. 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 https://cs.brown.edu/~rt/gdhandbook/
  2. Ioannis Tollis, Peter Eades, Giuseppe Di Battista, Roberto Tamassia, Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1998.

Verweise:

  • Link to the Eclipse Layout Kernel (ELK): https://www.eclipse.org/elk/
  • Link to Kiel Integrated Environment for Layout Eclipse RichClient (KIELER):

http://www.rtsys.informatik.uni-kiel.de/en/research/kieler.

Kommentar: