Our world is full of networks. The linking relationships might be quite abstract, such as friendship or metabolic processes or even more concrete, like roads or railways, but are still hard to overlook. One way to deal with such a network, is to mathematically model it as a graph with vertices representing the entities and edges the relationships. Graphs are widely used to visualize relational data. The area that deals with the theory and algorithmic questions of graph visualization is conventionally called graph drawing.

The usefulness of a drawing depends on aesthetic criteria as well as on the amount of information contained in the data which can be revealed by the drawing. Especially relevant for the readability is the minimization of edge crossings, which is why many methods yield intersection-free drawings if the input graph is planar. Yet the respective importance of the different criteria depends on the application. An aesthetically good drawing might not display relevant information or might even be misleading. A good vertex distribution for example can be helpful to overview a data set, but the relative closeness of objects might be interpreted as the strength of their relationship. Likewise, further information can be assigned not only to the elements, vertices and edges, but can also be displayed through their absolute and relative positions. Various criteria can be described by formal constraints. With the help of such geometric constraints, the graphs can meet the different requirements of concrete applications. In this thesis, various types of fundamental constraints on relevant classes of graphs are studied. For some problems efficient drawing algorithms could be developed, others were proven to be NP-hard, that is current state of research suggests that an efficient solution does not exist.

Netzwerke werden in den unterschiedlichsten Forschungsgebieten zur Repräsentation relationaler Daten genutzt. Durch geeignete mathematische Methoden kann man diese Netzwerke als Graphen darstellen. Ein Graph ist ein Gebilde aus Knoten und Kanten, welche die Knoten verbinden. Hierbei können sowohl die Kanten als auch die Knoten weitere Informationen beinhalten. Diese Informationen
können den einzelnen Elementen zugeordnet sein, sich aber auch aus Anordnung und Verteilung der Elemente ergeben.
Mit Algorithmen (strukturierten Reihen von Arbeitsanweisungen) aus dem Gebiet des Graphenzeichnens kann man die unterschiedlichsten Informationen
aus verschiedenen Forschungsbereichen visualisieren. Graphische Darstellungen
können das Verständnis von Datenmengen entscheidend unterstützen und bilden
eine hervorragende Basis f ur weitere Untersuchungen und neue Erkenntnisse.
Die Aussagekraft und der Informationsgehalt sowie die Verständlichkeit solcher Graphen hängen von verschiedenen Gesichtspunkten ab. Dazu gehören Knotenverteilung, Planarität (kreuzungsfreie Einbettung) und weitere ästhetische Eigenschaften. Die besonderen Informationskonstellationen und Strukturmerkmale
verschiedener Datenmengen erfordern Graphen, deren Darstellungsform der Problemstellung
angepasst ist. So ist es wichtig, effiziente Algorithmen zum Zeichnen von Graphen zu finden und zu untersuchen, die aufgrund der Anforderungen konkreter Anwendungen spezielle geometrische Eigenschaften haben. Für einige
Problemstellungen konnten im Rahmen dieser Arbeit Algorithmen zum automatisierten Zeichnen solcher Graphen entworfen werden. Bedingung für die entwickelten Methoden war die korrekte Wiedergabe der Daten, Optimierungsziel ist die Lesbarkeit. Für andere Probleme konnte deren Zugehörigkeit zur Komplexitätsklasse der NP-schweren Probleme bewiesen werden, was bedeutet, dass es kaum Ho nung auf eine effiziente und exakte Lösung gibt. Ist ein Problem als NP-schwer oder NP-vollständig bekannt, rechtfertigt dies eine Lockerung der Vorgaben, motiviert die Suche nach Heuristiken und Näherungsverfahren sowie nach anderen Anforderungen an die Zeichnung, welche eventuell ähnliche Vorteile für die Interpretation haben.