We describe an algorithm for the dominating set problem with time complexity O((4g+41)^kn^2) for graphs of bounded genus g, where k is the size of the set. It has previously been shown that this problem is fixed parameter tractable for planar graphs. Our method is a refinement of the earlier techniques.

The following paper was presented at SWAT 2002 and contains the main result for any graph of bounded genus.

J. Ellis, H. Fan and M. Fellows

Scandinavian Workshop on Algorithm Theory 2002, Lecture Notes in Computer Science 2368, pp. 180 - 189, Springer-Verlag, 2002.

This paper also contains a simpler proof for the previously known O(8^kn^2) result for planar graphs.

J. Ellis, H. Fan and M. Fellows

Journal of Algorithms, Vol. 52,2 pp. 152-168, 2004.