Planar domination graphs Original Research Article

A graph G is a domination graph if each induced subgraph of G has a pair of vertices such that the open neighborhood of one is contained in the closed neighborhood of the other in the subgraph. No polynomial time algorithm or hardness result is known for the problem of deciding whether a graph is a domination graph. In this paper, it is shown that the class of planar domination graphs is equivalent to the class of planar weakly chordal graphs, and thus, can be recognized in polynomial time.