Computing the Overlaps of Two Maps

Two combinatorial maps $$M_1$$M1 and $$M_2$$M2 overlap if they share a sub-map, called an overlapping pattern, which can be extended without conflicting neither with $$M_1$$M1 nor with $$M_2$$M2. Isomorphism and subisomorphism are two particular cases of map overlaps which have been studied in the literature. In this paper, we show that finding the largest connected overlap between two combinatorial maps is tractable in polynomial time. On the other hand, without the connectivity constraint, the problem is $$\mathcal {NP}$$NP-hard. To obtain the positive results we exploit the properties of a product map.