A polynomial algorithm for submap isomorphism of general maps

Combinatorial maps explicitly encode orientations of edges around vertices, and have been used in many fields. In this paper, we address the problem of searching for patterns in model maps by putting forward the concept of symbol graph. A symbol graph will be constructed and stored for each model map in the preprocessing. Furthermore, an algorithm for submap isomorphism is presented based on symbol sequence searching in the symbol graphs. The computational complexity of this algorithm is quadratic in the worst case if we neglect the preprocessing step.

► Put forward the concept of symbol graph of combinatorial maps. ► Convert the problem of submap isomorphism to the problem of sequence searching. ► Propose a quadratic algorithm for submap isomorphism based on sequence searching. ► Compared with existing algorithms, our algorithm is more general without any contraint on maps.