Polynomial algorithms for open plane graph and subgraph isomorphisms
| Autor: | Guillaume Damiand, Colin de la Higuera, ímilie Samuel, Christine Solnon, Jean-Christophe Janodet |
|---|---|
| Přispěvatelé: | Laboratoire d'Informatique de Nantes Atlantique (LINA), Mines Nantes (Mines Nantes)-Université de Nantes (UN)-Centre National de la Recherche Scientifique (CNRS), Informatique, Biologie Intégrative et Systèmes Complexes (IBISC), Université d'Évry-Val-d'Essonne (UEVE), Laboratoire Hubert Curien [Saint Etienne] (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet [Saint-Étienne] (UJM)-Centre National de la Recherche Scientifique (CNRS), Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), Laboratoire Hubert Curien (LHC), Institut d'Optique Graduate School (IOGS)-Université Jean Monnet - Saint-Étienne (UJM)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | angličtina |
| Rok vydání: | 2013 |
| Předmět: |
General Computer Science
0102 computer and information sciences 02 engineering and technology 01 natural sciences Theoretical Computer Science Combinatorics symbols.namesake Indifference graph Pathwidth Chordal graph 0202 electrical engineering electronic engineering information engineering Polynomial and NP-complete problems Cograph Open plane graphs Mathematics Discrete mathematics Trapezoid graph [INFO.INFO-RO]Computer Science [cs]/Operations Research [cs.RO] Subgraphs and patterns 1-planar graph Planar graph Modular decomposition Equivalence and isomorphism 010201 computation theory & mathematics symbols 020201 artificial intelligence & image processing MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Theoretical Computer Science Theoretical Computer Science, Elsevier, 2013, 498, pp.76-99. ⟨10.1016/j.tcs.2013.05.026⟩ Theoretical Computer Science, 2013, 498, pp.76-99. ⟨10.1016/j.tcs.2013.05.026⟩ |
| ISSN: | 1879-2294 0304-3975 |
| DOI: | 10.1016/j.tcs.2013.05.026⟩ |
| Popis: | International audience; Graphs are used as models in a variety of situations. In some cases, e.g. to model images or maps, the graphs will be drawn in the plane, and this feature can be used to obtain new algorithmic results. In this work, we introduce a special class of graphs, called open plane graphs, which can be used to represent images or maps for robots: they are planar graphs embedded in the plane, in which certain faces can be removed, are absent or unreachable. We give a normal form for such graphs and prove that one can check in polynomial time if two normalised graphs are isomorphic, or if two open plane graphs are equivalent (their normal forms are isomorphic). Then we consider a new kind of subgraphs, built from subsets of faces and called patterns. We show that searching for a pattern in an open plane graph is tractable if and only if the faces are contiguous, that is, we prove that the problem is NP-complete otherwise. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect