Planare Graphen mit kleiner Dilatation

Betrachtet man zwei Punkte in der Ebene, ist die Strecke zwischen ihnen bekanntlich die kürzeste Verbindung. In einem Graph G, der kreuzungsfrei und zusammenhängend in die Ebene eingebettet ist, kann man zwischen je zwei Knoten u und v zusätzlich den Graphabstand d_G(u,v) als die Länge des kürzesten Weges in G definieren, der u und v verbindet. Hierbei sollen die Kanten des Graphen Strecken in der Ebene entsprechen. Die Länge eines Weges im Graph ist die Summe der euklidischen Längen seiner Kanten. Die Dilatation ist ein Gütekriterium für Graphen. Je näher der Graphabstand zweier Punkte an ihrem euklidischen Abstand liegt, desto kleiner ist die Dilatation zwischen ihnen. Im Idealfall entspricht der Graphabstand dem euklidischen Abstand, d.h. die beiden Punkte sind durch eine Kante direkt verbunden. Die Dilatation zwischen ihnen ist eins. Gilt dies für alle Knoten des Graphen und ist der Graph planar, hat er eine bestimmte Struktur. Diese Struktur sowie die Struktur von Graphen mit Dilatation minimal größer eins, wird in diesem Buch untersucht. Weiterhin wird eine Konstruktionsvorschrift für letztere angegeben.

Autorentext

Studium der Mathematik an der Freien Universität Berlin von 2000 bis Mitte 2006, Wissenschaftliche Mitarbeiterin des Instituts für Luft- und Raumfahrt der Technischen Universität Berlin am Fachgebiet Flugführung und Luftverkehr von Mitte 2006 bis Ende 2007, Seit Anfang 2008 Mitarbeiterin der Jamba! GmbH, Betreuung des Data Mining.