A Polynomial Algorithm for Subisomorphism of Open Plane Graphs - Archive ouverte HAL Access content directly
Conference Papers Year : 2009

A Polynomial Algorithm for Subisomorphism of Open Plane Graphs

(1) , (2) , (2) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
conf-2009-mlg.pdf (116.21 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

ujm-00411610 , version 1 (09-06-2011)

Identifiers

  • HAL Id : ujm-00411610 , version 1

Cite

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⟩
324 View
248 Download

Share

Gmail Facebook Twitter LinkedIn More