A Polynomial Algorithm for Subisomorphism of Open Plane Graphs

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

1 M2DisCo - Geometry Processing and Constrained Optimization
2 LHC - Laboratoire Hubert Curien
3 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information

We address the problem of searching for a pattern in a plane graph, that is, a planar drawing of a planar graph. We define plane subgraph isomorphism and give a polynomial algorithm for this problem. We show that this algorithm may be used even when the pattern graph has holes.

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

Guillaume Damiand, Colin de La Higuera, Jean-Christophe Janodet, Émilie Samuel, Christine Solnon. A Polynomial Algorithm for Subisomorphism of Open Plane Graphs. Mining and Learning with Graphs (MLG), Jul 2009, Leuven, Belgium. pp.mlg09-11. ⟨ujm-00411610⟩