TITLE:Compact Routing Tables for Graphs of Bounded Genus
AUTHORS:Cyril Gavoille and Nicolas Hanusse
ABSTRACT:
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(log2+en)
bit-operations per node to extract the route, with constant
e>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 g, g >=0, by building shortest path routing
tables of nlog(g+1)+O(n) bits per node, and with
O(log2+en) 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.