Meshing with Distances

Abstract

A concept from Gary Chartrand and Ping Zhang’s book “A First Course In Graph Theory” is that there is a second way of measuring distance in graphs, and that is the detour distance. The detour distance between two arbitrary vertices is the length of the longest path between those vertices. Another way of measuring distance in a graph is the directed distance which is the length of the shortest path between two vertices. This topic extends the concept of distance in graphs to provide more flexibility when modeling with graphs. In this presentation we consider results concerning detour distances within Mesh graphs, which have similar characteristics to that of city grid systems.