A Polynomial Algorithm for Subisomorphism of Open Plane Graphs

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

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⟩

Share

Metrics

Record views

597

Files downloads

260