Automatisches Zeichnen von Graphen Show URL Convert to PDF XML representation

 

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: IG (MSc Inf.) MV (MSc Inf.) WI (MSc WInf. (15)) IS (MSc Inf.) WI (MEd Inf) WPI (MEd Inf) IG (TA) (MSc Inf (2-Fach)) IS (SA) (MSc Inf (2-Fach)) IG (SA) (MSc Inf (2-Fach)) WI (MSc Inf (15))
Lehrsprache: Englisch

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
  • Extend existing approaches for specific 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 or to develop new approaches. Finally, students should also be able to perform a thesis project (Bachelor or Master) on the subject of graph drawing and to contribute to ELK and KIELER.

Lehrinhalte:

  • 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

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:

The grade is determined by a final exam. Prerequisite for admission to exam: received at least 50% of homework assignment points.

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: