We 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 we propose the class of quasi-planar graphs and in three dimensions the class of quasi-polyhedral graphs. In both cases we provide a routing algorithm that guarantees delivery. Our algorithms need only "remember" the source and destination nodes and one (respectively, two) reference nodes. Moreover, we 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.

Additional Metadata
Persistent URL dx.doi.org/10.1109/PERCOMW.2006.107
Conference 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006
Citation
Kranakis, E, Mott, T. (Tim), & Stacho, L. (Ladislav). (2006). Online routing in quasi-planar and quasi-polyhedral graphs. Presented at the 4th Annual IEEE International Conference on Pervasive Computing and Communications Workshops, PerCom Workshops 2006. doi:10.1109/PERCOMW.2006.107