# Is the dominating set problem restricted to planar bipartite graphs of maximum degree 3 NP-complete?

Does anyone know about an NP-completeness result for the DOMINATING SET problem in graphs, restricted to the class of planar bipartite graphs of maximum degree 3?

I know it is NP-complete for the class of planar graphs of maximum degree 3 (see the Garey and Johnson book), as well as for bipartite graphs of maximum degree 3 (see M. Chlebík and J. Chlebíková, "Approximation hardness of dominating set problems in bounded degree graphs"), but could not find the combination of the two in the literature.

-
The minimum edge dominating set is NP-hard in bipartite graphs of maximum degree 3, but I think this doesn't help with your problem. Posting at cstheory.stackexchange.com might widen the pool of experts... –  Joseph O'Rourke Oct 27 '10 at 1:04
Ok thanks - I just heard about this website, I didn't know there are other similar ones ;) –  Florent Foucaud Oct 27 '10 at 11:29
And here is the link: cstheory.stackexchange.com/questions/2505/… –  Jukka Suomela Oct 27 '10 at 17:31
The problem remains NP-complete even for planar bipartite graphs of maximum degree 3. See the nice reduction by @Jukka Suomela at cstheory.stackexchange.com/questions/2505/… which works by introducing 3 new vertices in each edge. –  András Salamon Mar 18 '11 at 18:31