Skip to Main content Skip to Navigation
Conference papers

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
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 metadata

Cited literature [8 references]  Display  Hide  Download
https://hal-ujm.archives-ouvertes.fr/ujm-00411610
Contributor : Émilie Samuel Connect in order to contact the contributor
Submitted on : Thursday, June 9, 2011 - 1:23:54 PM
Last modification on : Saturday, June 25, 2022 - 7:25:31 PM
Long-term archiving on: : Saturday, September 10, 2011 - 2:20:13 AM

File

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

Identifiers

  • HAL Id : ujm-00411610, version 1

Collections

UNIV-ST-ETIENNE | CNRS | UNIV-LYON1 | UNIV-LYON2 | INSA-LYON | EC-LYON | LAHC | LIRIS | LABEXIMU | INSA-GROUPE | UDL | ANR

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 Datacite

Share

Metrics

Record views

323

Files downloads

246