Graphzeichnen

Das Graphzeichnen (engl. Graph Drawing) ist ein Themengebiet der Informatik und der Diskreten Mathematik, das sich damit beschäftigt, Graphen geometrisch zu realisieren. Eine zentrale Rolle beim Graphzeichnen bilden Algorithmen, die für einen gegebenen Graphen eine 2-dimensionale Einbettung in den Euklidischen Raum berechnen. Die Knoten des Graphen werden in der Regel durch einfache geometrische Objekte wie Punkte, Kreise oder Quadrate realisiert. Gibt es eine Kante zwischen zwei Knoten, wird dies in der Zeichnung durch eine Jordan-Kurve dargestellt, welche die den Knoten zugeordneten Objekte verbindet. Das Graphzeichnen ist in zwei Felder unterteilt: Im statischen Graphzeichnen soll ein Graph dargestellt werden, während im dynamischen Graphzeichnen ganze Sequenzen von Graphen (meist in einer Animation) visualisiert werden sollen.