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.
Document type :
Conference papers
Complete list of metadatas

Cited literature [8 references]  Display  Hide  Download
https://hal-ujm.archives-ouvertes.fr/ujm-00411610
Contributor : Émilie Samuel <>
Submitted on : Thursday, June 9, 2011 - 1:23:54 PM
Last modification on : Tuesday, February 26, 2019 - 4:26:15 PM
Long-term archiving on : Saturday, September 10, 2011 - 2:20:13 AM

File

conf-2009-mlg.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : ujm-00411610, version 1

Collections

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

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. ⟨ujm-00411610⟩

Export

BibTeX TEI DC DCterms EndNote

Share

Metrics

Record views

597

Files downloads

260

Contact

CCSD