Compact Routing Tables for Graphs of Bounded Genus
Cyril Gavoille, Nicolas Hanusse · 1999
For planar graphs on n nodes we show how to construct in linear time shortest path routing tables that require 8n + o(n) bits per node, and O(log 2+ffl n) bit-operations per node to extract the route, with constant ffl ? 0. We generalize the result for every graph of bounded crossing-edge number. We also extend our result to any graph of genus bounded by fl, fl ? 0, by building shortest path routing tables of n log (fl + 1) + O(n) bits per node, and with O(log 2+ffl n) bit-operations per node to extract the route. This result is obtained by the use of dominating sets, compact coding of non-crossing partitions, and k-page representation of graphs.