Perfect matching in a graph is a set of edges where any pair does not share a common vertex and every vertex of the graph is the endpoint of an edge from that set. From the paper's introduction: "A polyomino graph is a connected finite subgraph of the infinite plane grid such that each finite face is surrounded by a regular square of side length 1 (called a cell) and each edge belongs to at least one cell." It has been an open problem whether finding a perfect matching of a polyomino can be done using an algorithm that runs in linear time in the number of vertices, and this paper offers a solution.
展开▼
