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.