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 SIC
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
2 LHC - Laboratoire Hubert Curien [Saint Etienne]
3 LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
Abstract : 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.
Type de document :
Communication dans un congrès
Mining and Learning with Graphs (MLG), Jul 2009, Leuven, Belgium. pp.mlg09-11, 2009
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger
https://hal-ujm.archives-ouvertes.fr/ujm-00411610
Contributeur : Émilie Samuel <>
Soumis le : jeudi 9 juin 2011 - 13:23:54
Dernière modification le : mercredi 25 juillet 2018 - 14:05:30
Document(s) archivé(s) le : samedi 10 septembre 2011 - 02:20:13

Fichier

conf-2009-mlg.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : ujm-00411610, version 1

Collections

UNIV-LYON2 | EC-LYON | LAHC | LIRIS | UNIV-ST-ETIENNE | INSA-LYON | UNIV-LYON1 | IOGS | PARISTECH

Citation

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, 2009. 〈ujm-00411610〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

552

Téléchargements de fichiers

242

Contact

support.ccsd.cnrs.fr
hal.support@ccsd.cnrs.fr
Logo CCSD