Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images

Guillaume Damiand (1) , Colin de La Higuera (2) , Jean-Christophe Janodet (2) , Émilie Samuel (2) , Christine Solnon (1)

1 M2DisCo - Geometry Processing and Constrained Optimization
2 LHC - Laboratoire Hubert Curien

In this paper, we address the problem of searching for a pattern in a plane graph, i.e., a planar drawing of a planar graph. To do that, we propose to model plane graphs with 2-dimensional combinatorial maps, which provide nice data structures for modelling the topology of a subdivision of a plane into nodes, edges and faces. We define submap isomorphism, we give a polynomial algorithm for this problem, and we show how this problem may be used to search for a pattern in a plane graph. First experimental results show the validity of this approach to efficiently search for patterns in images.

Domaines: Algorithme et structure de données [cs.DS]

Guillaume Damiand, Colin de La Higuera, Jean-Christophe Janodet, Émilie Samuel, Christine Solnon. Polynomial Algorithm for Submap Isomorphism: Application to searching patterns in images. Graph-based Representations in Pattern Recognition (GbRPR), May 2009, Venise, Italy. pp.102-112, ⟨10.1007/978-3-642-02124-4_11⟩. ⟨ujm-00389763⟩