Diagrama de temas

  • General

  • Seminar: Visualisierung von Graphen in 3D

    Umfang:

    5 ECTS

    Zeit & Ort:

    Freitag, 26.04.2019, 12:15–13:45 Uhr, ÜR II
    Freitag, 03.05.2019, 12:15–13:45 Uhr, ÜR II
    Freitag, 12.07.2019,  13:00–17:00 Uhr, ÜR II
    Freitag, 19.07.2019,  13:00–17:00 Uhr, ÜR II

    Voraussetzung:  

    Algorithmische Graphentheorie (mit Nachdruck empfohlen)

    Zielgruppe:

    Master Informatik (vorzugsweise), Bachelor Informatik

    Dozenten:

    Alexander Wolff und Johannes Zink

    Kooperationspartner:    

    Infosim (Würzburg) und denkbares (Würzburg)

    Der erste Termin ist am Fr, 26.04.2019. An diesem Termin besprechen wir den Ablauf des Seminars und stellen die Vortragsthemen vor. Aus diesem Grund bitten wir um vollständige Anwesenheit .

    Bitte schreiben Sie sich schon vorher in diesen Wuecampus-Kurs ein, falls Sie am Seminar teilnehmen wollen.
    (Klicken Sie dazu im Kursraum ganz oben links auf das Feld mit den weißen Zahnrädern auf blauem Grund und wählen Sie dann "Mich in diesem Kurs einschreiben" aus.) 

    • Überblick

      Wir beschäftigen uns mit Algorithmen zum Zeichnen von Graphen in 3D. Das ist ein Thema, welches bislang weniger Beachtung in Forschung, Literatur und Praxis erfahren hat. Dort geht es in den allermeisten Fällen um das Zeichnen von Graphen in 2D. Dies ist insofern nachvollziehbar, als die klassischen zweidimensional Darstellungsmedien wie Papier, Poster oder Bildschirme seit langem in unserem Alltag sehr präsent sind und es auch weiterhin sein werden. Neben diesen klassischen Darstellungsmedien erfreuen sich seit einigen Jahren aber auch neue dreidimensionale Medienkonzepte wie Virtual Reality oder Hologramme zunehmend größerer Beliebtheit. Dieses Seminar soll daher ein Anknüpfungspunkt sein, um einen Einblick in die vorhandene Literatur mit ihren Konzepten und Umsetzungen zum Visualisieren von Graphen in 3D zu erlangen.

      Das Seminar wird in Kooperation mit den zwei Würzburger IT-Unternehmen Infosim und denkbares durchgeführt, welche auch teilweise die Betreuung bestimmter Themen übernehmen und zu denen so auch ein Kontakt hergestellt und ein Einblick auch für etwaige spätere Tätigkeiten gewonnen werden kann.

      Themen

      Themen sind sowohl alte Arbeiten zu den Grundlagen zum Zeichnen von Graphen in 3D als auch neue Ergebnisse, sodass alle Teilnehmer und Teilnehmerinnen durch die eigene Arbeit und das Hören der anderen Vorträge einen hilfreichen Überblick in die 3D-Visualisierung von Graphen bekommen sollen. Für jedes Thema geben wir einen Artikel bzw. ein Buchkapitel vor. Sie sollen aber auch noch selbst Literaturrecherche betreiben. Ein Ausgangspunkt dafür können beispielsweise die Referenzen in ihrem Artikel sein. Da wir das Seminar auch auf die aktuelle Forschung hin ausrichten wollen, sind insbesondere offene Fragen ein wichtiger Bestandteil der Themen. Wenn es das eigene Thema anbietet, so können und sollen auch selbst die untersuchten Konzepte einmal grob implementiert werden bzw. vorhandene Programme einmal ausprobiert werden. Dies kann dann als kleine Demonstration Teil des Abschlussvortrags gegen Ende des Semesters sein und möglicherweise als Grundlage für weitere Arbeiten dienen.

      Thema
      		Autoren
      		Artikel
      		Konferenz/Journal  Link  Bearbeitet Betreut
      		 Vortragstermin
      Motivation für 3D
          (Benutzerstudien)
      		C. Ware, G. Franck
        und
      C. Ware, P. Mitchell
        und
      O.-H. Kwon, C. Muelder, K. Lee, K.-L. Ma
      		Evaluating Stereo and Motion Cues for Visualizing     
          Information Nets in Three Dimensions
      Visualizing Graphs in Three Dimensions

      A Study of Layout, Rendering, and Interaction
          Methods for Immersive Graph Visualization
      		ACM Trans. Graphics '96

      ACM Trans. Appl. Percept. '08

      IEEE Tran. on Vis. & Comp. Graphics '16
      		hier

      hier

      hier

      		 PS  Infosim 12.07.2019
      Überblick über 3D-Bibliotheken
          (freie Recherche)
      		 –
      		 –
      		 –
      		 –  SL  Infosim 19.07.2019
      VLSI-Design in 3D
      		F. T. Leighton, A. L. Rosenberg
      		Three-Dimensional Circuit Layouts
      		SIAM J. Comput. '86
      		hier
      		 BR  A. Wolff
      		 19.07.2019
      Volumen von Zeichnungen allgemeiner und planarer Graphen
      		R. E Cohen, P. Eades,
          T. Lin, E. Ruskey
      		Three-Dimensional Graph Drawing
      		Algorithmica '96
      		hier  FK  O. Firman
      		 12.07.2019
      Volumen und Färbbarkeit
      		J. Pach, T. Thiele, G. Tóth
      		Three-Dimensional Grid Drawings of Graphs
      		Adv. in Disc. & Comp. Geom. '99
      		hier
      		 JG  A. Wolff
      		 19.07.2019
      Notwendiges Volumen
      		J. Bose, J. Czyzowicz,
          P. Morin, D. R. Wood
      		The Maximum Number of Edges in a
          Three-Dimensional Grid-Drawing
      		J. of Graph Algo. & Appl. '98
      		hier
      		 PT  J. Zink
      		 19.07.2019
      Track-Zahl, Knotenfärbung     
      		V. Dujmović, P. Morin, D. R. Wood
      		Layout of Graphs with Bounded Tree-Width
      		SIAM J. of Computing '05
      		hier
      		 MK & YR
      		 J. Zink
      		 12.07.2019
      Geometrische vs. allgemeine Thickness
      		D. Eppstein
      		Separating Thickness from Geometric Thickness
      		Towards a Theo. of Geom. Graphs '04     
      		hier
      		 YA  S. Chaplick
      		 19.07.2019
      Orthogonale Gitterzeichnungen  
      		P. Eades, A. Symvonis, S. Whitesides
        und
      D. R. Wood
      		Three-dimensional orthogonal graph drawing algorithms

      Optimal three-dimensional orthogonal graph drawing in the general position model
      		Discrete Applied Mathematics '00

      Theoretical Computer Science '03
      		hier

      hier
      		 BH  J. Zink
      		 19.07.2019
      Ästhetikmaße in 3D
          (Freie Literaturrecherche,
           möglicher Ausgangspunkt:)
      		V. Dujmović, P. Morin, D. R. Wood
          (enthält aspect ratio und zählt
          ein paar Kriterien auf)
      		Pathwidth and Three-Dimensional
          Straight-Line Grid Drawings of Graphs
      		Proc. 10th Int. Symp. on Graph
          Drawing (GD) '02
      		hier  ML  denkbares 
      		 –
      Graphen als 3D-Landschaften
      		M. Gronemann, M. Jünger
      		Drawing Clustered Graphs as Topographic Maps
      		Proc. 20th Int. Symp. on Graph
          Drawing (GD) '12
      		hier
      		 DB  denkbares 12.07.2019
      Graphen als Landkarten
      		E. R. Gansner, Y. Hu, S. G. Kobourov
      		GMap: Drawing Graphs as Maps Proc. 17th Int. Symp. on Graph
          Drawing (GD) '09
      		hier  KM  denkbares 12.07.2019

      Die Artikel können Sie über die Links herunterladen, die meisten auch außerhalb des Uninetzes. Anderenfalls wenden Sie sich an uns.

      Lernziele

      Die Teilnehmer und Teilnehmerinnen lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmern in einem Vortrag zu vermitteln.

      Sie bekommen im Seminar einen Überblick über Techniken der Graphvisualisierung in 3D und vertiefen ihre Kenntnisse über das Modellieren und Lösen von Problemen mithilfe von Graphen und Graphalgorithmen. Dieses Thema eignet sich übrigens auch gut für Abschlussarbeiten.

      Außerdem sollen sie einen Eindruck von Forschung in der Informatik bekommen: vom Erkennen und Formulieren geeigneter Problemstellungen über das Entwickeln von Lösungsstrategien für diese Probleme bis zum Festhalten der Ergebnisse in einer wissenschaftlichen Arbeit.

      Module

      Unser Seminar richtet sich in erster Linie an Studenten und Studentinnen im Master Informatik, welche wir bei der Themenwahl evtl. bevorzugen werden.
      Darüber hinaus können aber auch interessierte Studenten und Studentinnen im Bachelor Informatik (oder ähnliches) daran teilnehmen.
      Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar für den Bachelor- oder Masterstudiengang Informatik eingetragen. Bei großem Engagement über den Vortrag und die Ausarbeitung hinaus (siehe Ablauf), wäre auch eine Anrechnung als Praktikum denkbar.

      Allgemeine Literatur zum Graphzeichnen in 3D

  • Ablauf

    1. Im ersten Treffen am Freitag, den 26.04.2019 werden wir einen kurzen Überblick über die möglichen Themen geben und diese auf die Teilnehmer verteilen. Davor werden wir den Ablauf des Seminars erklären.
    2. Im zweiten Treffen am Freitag, den 03.05.2019 gibt jeder Teilnehmer einen kurzen Überblick über sein Thema (max. 5 Minuten, 3 Folien). Außerdem werden wir Genaueres zur Gestaltung der Vorträge und der Ausarbeitung sagen.
      Nach den Kurzvorträgen soll die Zuweisung der Betreuung stattfinden. Mögliche Betreuer sind Mitarbeiter oder Mitarbeiterinnen der Unternehmen Infosim und denkbares sowie des Lehrstuhls für Informatik I.
    3. Eine erste Version der schriftlichen Ausarbeitung soll bis 12.06.2019 dem Betreuer vorgelegt werden. Dieser gibt dann Feedback, das in die finale Version eingebracht werden soll. Die finale Version ist bis zum 23.06.2019 abzugeben.
    4. Die folgenden Treffen im Juli gegen Ende des Semesters sind als Blockveranstaltung für die eigentlichen Vorträge der Teilnehmer gedacht. Neben dem Vortrag bleibt auch Zeit zur Diskussion der Themen und daraus resultierender offener Fragen für mögliche weitere Forschung.
    5. Darüber hinaus besteht die Möglichkeit weiter an den untersuchten und vorgestellten Themen zu arbeiten und zu forschen.
      Das kann im Rahmen einer Tätigkeit am Lehrstuhl für Informatik I sein, ggf. zusammen mit oder bei Infosim oder denkbares.

  • Termine

    Termin Thema Vortragende   
    		Anmerkungen
    26.04.2019 Einführung
    		LS1, Infosim, denkbares   
    		Vergabe der Themen
    03.05.2019 Kurzvorträge Alle Zuweisung der Betreuer
    12.06.2019
    		 Vorlage der vorläufigen Ausarbeitung beim Betreuer   
    		   
    23.06.2019
    		 Abgabe der schriftlichen Ausarbeitung
    		    
    30.06.2019 Vorlage der vorläufigen Folien beim Betreuer
    		PS, FK, KM, DB, MK & YR
    07.07.2019
    		 Vorlage der vorläufigen Folien beim BetreuerBR, JG, PT, BH, YA, SL
    12.07.2019 Blockvorträge
    		PS, FK, KM, DB, MK & YR
    19.07.2019 Blockvorträge
    		BR, JG, PT, BH, YA, SL

    • Ausarbeitungen

      Die Ausarbeitung zu ihrem Thema sollte etwa 10 Seiten (zuzüglich Titelseite) umfassen. Sie soll nicht nur den von uns vorgegebenen Artikel zusammenfassen, sondern auch darüber hinaus gehen. Zum Einen eignet sich dafür das Material, das sie durch eigene Literaturrecherche gefunden haben. Zum anderen kann man hier auch auf interessante offene Fragen eingehen.

      Die Themen des Seminars sollen nicht für sich alleine stehen, sondern wurden bewusst aus einem bestimmten Gebiet gewählt. Nutzen Sie das in ihrer Ausarbeitung und zeigen Sie Verbindungen zu anderen Vortragsthemen des Seminars auf! Vielleicht können Sie dadurch auch neue Fragestellungen entwickeln, die für die weitere Forschung interessant sind.

      Die Ausarbeitungen sollen mit LaTeX erstellt werden. Wenn Sie noch keine Erfahrung mit LaTeX haben, könnte ein kostenloser LaTeX-Kurs im Rechenzentrum hilfreich sein.

    • Vorträge

      • Ihr Vortrag sollte 25–30 Minuten dauern und auch nicht länger sein (45–50 Minuten bei zwei Personen mit einem Thema).
      • Wir empfehlen für die Erstellung der Folien das kostenlose Programm ipe (verfügbar für Linux, Windows, Mac).
        Im Vergleich zu Powerpoint erleichtert es die Mischung von Text und Bildern. Man kann mit ipe geometrisch konstruieren und LaTeX-Befehle verwenden.
      • Ihr Vortrag kann auch offene Probleme ansprechen und vorhandene Programme/Demonstratoren können gezeigt werden.
      • Die Folien ihres Vortrages stellen wir hier für alle Teilnehmer des Seminars zur Verfügung.
      • Vortragsfolien Carpeta
        Restringido No disponible hasta que: se pertenezca al grupo Seminarteilnehmer