Online routing algorithms on geometric graphs with convex substructures

In this thesis we describe five new algorithms (QUASI-PLANAR, QUASI-POLYHEDRAL, QFQ, SPIRAL, DOUBLE-CROSSING) for online route discovery on several classes of geometric graphs. We propose the classes of quasi-planar graphs in R2, which consist of underlying convex embeddings with arbitrary chords added to each face, and, analogously, quasi-polyhedral graphs in R3. QUASI-PLANAR and QUASI-POLYHEDRAL guarantee delivery on quasi-planar and quasi-polyhedral graphs, respectively. Inspired by the well-known GFG algorithm for unit disk graphs, we create a hybrid algorithm, QFQ, that uses QUASI-PLANAR as a subroutine, and guarantees delivery on quasi-planar and unit disk graphs. SPIRAL is a geocasting algorithm for quasi-planar graphs: it visits every vertex in a specified bounded convex region. Finally, the DOUBLE-CROSSING algorithm finds three vertex-disjoint s,t-paths in a convex embedding.