Joint Tree of Combinatorial Maps

Combinatorial maps are widely used in the field of computer vision, including image segmentation, medical image analysis and mobile robotics. Many practical problems can be formulated as the combinatorial map matching problem. This paper addresses the problem of inexact matching between labeled combinatorial maps. We define Joint Tree of combinatorial maps, and prove it can be used to decide of map isomorphism. In this way, the map matching problem is relaxed to the Joint Tree matching problem, which can be solved in polynomial time. Our approach provides a novel way to explore the problem of combinatorial map matching.