Institut für Theoretische Informatik, Algorithmik
Suche
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Institut für Theoretische Informatik, Algorithmik
Lehre
Wintersemester 2018/19
Algorithmen zur Visualisierung von Graphen

Algorithmen zur Visualisierung von Graphen

Wintersemester 2018/19

Allgemeines

  • Skript: Die Vorlesung orientiert sich an der dem Skript (nur für Hörer zugänglich), zusätzlich gibt es ergänzendes Material
  • Credits: Es werden für diese Vorlesung 5 Leistungspunkte vergeben
  • Module: Die Vorlesung kann in dem Modul T-INFO-104390 geprüft werden
  • Sprache: Vorlesung: Englisch, Übung: Deutsch

Aktuelles

  • 21.12.2018 Dates for the exercise sessions updated.
  • 21.12.2018 Instances for the practical task are online.
  • 13.11.2018 Examination Dates: February 19 and March 26 (fully booked), 9:00-12:00. To register please send an email to: sekr [dash] wagner [at] ira [dot] uka [dot] de. In case of full booking other dates will be offered.
  • 16.10.2018 Drawthese graphs as nice as possible and keep the list of properties that you optimize to achieve a nice layout. Send the exported pictures to Tamara by email. We will discuss the pictures on 17.10.2018.
  • 30.10.2018 Die zweite Übung findet erst am 14.11 statt!

Thema

Das Graphenzeichnen beschäftigt sich mit der geometrischen Repräsentation von Graphen und Netzwerken und wird durch jene Anwendungen motiviert, in denen eine Visualisierung struktureller Informationen als Graph unentbehrlich ist. Das Gebiet erstreckt sich von rein theoretischen Aspekten bis hin zu Implementationen denen man im Alltag begegnet. Ergebnisse aus dem Feld des Graphenzeichnens stellen Schlüsselfaktoren dar, in Gebieten wie Web Computing, E-Commerce, VLSI, Schaltungsentwurf, Informationssysteme, Software Engineering, Algorithmische Kartographie, Bioinformatik, Netzwerktechnik und soziale Netzwerkanalyse.

Practical Task

  • Topic: Metro-map metaphor for hypergraph visualization
  • Duration: December 19 - February 19
  • Work in groups of 2-3
  • Presentation of ideas: 29th of January
  • Introduction slides
  • Graph Layout based on dimensionality reduction paper
  • Instances

Vorlesungen & Übungen

Vorlesungen und Übungen werden voraussichtlich an den folgenden Terminen stattfinden (Änderungen vorbehalten).

Datum Thema Folien Literatur
Di, 16.10. 1. Vorlesung Introduction slides
Mi, 17.10. 2. Vorlesung Drawing conventions and aesthetics. Level-based layout for trees. slides [BETT99] Chapter 3.1.2, Skript: Chapter 6.1
Di, 23.10. -
Mi, 24.10. 1. Übung
Di, 30.10. 3. Vorlesung Tree layouts. Series-parallel graphs tree layouts series-parallel graphs Trees: [BETT99] Chapters 3.1.3-4, Skript: page 86, Chapter 6.1.2. Additional [SR83] S-P: [BETT99] Chapter 3.2, 11.1, Skript: Chapter 6. Additional [HEL00], [EH13]
Di, 06.11. 4. Vorlesung Planar Straight-line drawings. Shift Method. slides [NR04] Chapter 4.2.
Di, 13.11. 5. Vorlesung Planar Straight-line drawings. Realizer Method. slides [NR04] Chapter 4.3
Mi, 14.11. 2. Übung Series-Parallel Graphs, Canoncial Order
Di, 20.11. 6. Vorlesung Force Directed Layouts. slides Skript Kap. 2
Mi, 21.11. 3. Übung
Di, 27.11. - -
Di, 04.12. 7. Vorlesung Layered Layout 1. slides Chapter 5. [BETT99] Chapter 9.
Di, 11.12. 8. Vorlesung Layered Layout 2. slides
Di, 18.12. 9. Vorlesung Orthogonal Layout (Incremental) slides Skript Kap. 7
Di, 08.01. 10. Vorlesung Orthogonal Layout (Flow) slides Skript: Chapter 4. [BETT99] Chapter 5.
Mi, 09.01. 4. Übung
Di, 15.01. 11. Vorlesung Upward Planar Drawings. slides Skript: Chapter 4.3.1-4.3.2. [BETT99] Chapter 6.
Mi, 16.01. 5. Übung
Di, 22.01. 12. Vorlesung Contact Representations. slides [He93],[HK94](Section 4)
Di, 29.01. 13. Vorlesung Wrap-up and overview.
Mi, 30.01. 6. Übung

Übungsblätter

Blatt Hinweis Ausgabe Diskussion
1. Übungsblatt Werfen Sie schon einmal einen Blick auf die dritte Vorlesung 16.10 24.10
2. Übungsblatt Termin der Übung wurde verschoben! 30.10 14.11
3. Übungsblatt 15.11 21.11
4. Übungsblatt 06.12 09.01
5. Übungsblatt 21.12 16.01
6. Übungsblatt 16.01 30.01

Practical Task - Tools and Instances

Try your algorithm on the following hypergraph datasets.

SAT

A SAT formula in disjunctive normal form (DNF) can be interpreted as a hypergraph. Each clause C corresponds to a vertex v_C and each variable x to a hyperedge e_x. A hyperedge v_x contains a clause v_C if and only if the variable x occurs (in positive or negative form) in the clause C. The SAT computation challenge[1] lists a variety of SAT instances. Try to visualize as many as possible, start with change t small instances. The instances are encoded in the DIMACS format.

Datasets

Random Hypergraphs

This dataset of hypergraphs was generated randomly. The set consists of small, medium and a few large graphs. Again, the instances are encoded in the DIMACS format. Note that vertices of degree 0 are allowed.

Dataset

Be Creative

There is a class of hypergraphs you wanted to visualize since you were a child? Here is your opportunity. Find an interesting dataset, model it as a hypergraph and visualize it with your algorithm!

Tools

The following tools are able to visualize graphs (not necessarily hypergraphs).

Literatur, Skripte, Zusatzmaterial

[BBN+13] T. Biedl, T. Bläsius, B. Niedermann, M. Nöllenburg, R. Prutkin, I. Rutter: Using ILP/SAT to determine pathwidth, visibility representations, and other grid-based graph drawings, In: Graph Drawing, LNCS 8242, pp.460-471, Springer 2013.
[BETT99] G. Di Battista, P. Eades, R. Tamassia, I. G. Tollis: Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.
[ELS93] P. Eades, X. Lin, W. F. Smyth: A fast and effective heuristic for the feedback arc set problem, Information Processing Letters, 47(6):319–323, 1993
[EW94] Eades, P., Wormald, N. C.: Edge crossings in drawings of bipartite graphs. Algorithmica, 1994, 11(4):379–403.
[KW01] M. Kaufmann, D. Wagner: Drawing Graphs: Methods and Models, Springer-Verlag, 2001
[HK94] X. He, G. Kant Two algorithms for finding rectangular duals of planar graphs, LNCS, Springer, Vol. 790, pages 396-410, 1994
[He93] X. He On Finding the Rectangular Duals of Planar Triangular Graphs, SIAM J. Comput., Vol. 22(6), pages 1218–1226, 1993
[EH13] P. Eades, S. Hong Symmetric Graph Drawing Handbook of Graph Drawing and Visualization 2013: 87-113
[HEL00] S. Hong, P. Eades, S. Lee: Drawing Series-Parallel Digraphs Symmetrically, Computational Geometry, Vol. 17, Issues 3–4, pages 165–188, 2000
[LY07] C. Lin, H. Yen: On Balloon Drawings of Rooted Trees, JGAA, vol.11, no.2, pp.431-452
[NR04] T. Nishizeki, Md. S. Rahman: Planar Graph Drawing, World Scientific, 2004
[NW11] M. Nöllenburg, A. Wolff: Drawing and Labeling High-Quality Metro Maps by Mixed-Integer Programming, In: IEEE Transactions on Visualization and Computer Graphics 17(5):626-641, 2011.
[T13] R. Tamassia: Handbook of Graph Drawing and Visualization, CRC Press, 2013.
[SR83] K. J. Supowit, E. M. Reingold The complexity of drawing trees nicely Acta Informatica, Volume 18, Issue 4, pp 377–392