maximum number of dominoes can be placed inside a figure

Question

Suppose some figure on the squared paper. Sides of the figure go straight on the lines of squared paper. Figure may have any (not even convex) shape. How to find the maximum number of dominoes (1x2 rectangular) that can be placed in that figure. It is not allowed to put domino over another one. It is allowed to put domino only in such way, when its sides fall exactly on the lines of squared paper.

Answer 1

Looks like the maximum cardinality matching problem in a bipartite graph. The squares are the vertices and the dominoes are the edges that belong to the matching.

To see that the graph is bipartite, imagine the squares are checkerboard-painted. Black ones only neighbour white ones and vice versa.