Planare Graphen mit kleiner Dilatation, Fachbücher

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.