Any n-dimensional grid (sometimes called a "Manhattan space") is a bipartite graph. You may find it useful that no odd-length cycles can exist in such a graph.
There are many reasons why you would want a maximal matching. In my case I was working on a distributed system prototype that needed to match block requests my users to cache servers. This is a maximal matching from cache servers who have these blocks available to users requesting blocks.
