Online Routing in Quasi-Planar and Quasi-Polyhedral Graphs
The authors address the problem of online route discovery for a class of graphs that can be embedded either in two or in three dimensional space. In two dimensions they propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In both cases they provide a routing algorithm that guarantees delivery. Their algorithms need only "Remember" the source and destination nodes and one (respectively, two) reference nodes. Moreover, they show that the quasi-planar routing algorithm is inherently flexible in its path-finding, and as an application demonstrate computational results for a network load problem.