An approach to the subgraph homeomorphism problem
type: Item
instance of: scholarly article
title: An approach to the subgraph homeomorphism problem
zbMATH Open document ID: 0572.68052
DOI: 10.1016/0304-3975(85)90222-1
author: T. Asano
published in: Theoretical Computer Science
publication date: 1985-01-01T00:00:00Z
review text: The subgraph homeomorphism problem for a fixed pattern graph H is stated as follows: given an input graph \(G=(V,E)\), determine whether G has a subgraph homeomorphic to H. We show that the subgraph homeomorphism problem for the fixed graph \(K_{3,3}\) is solvable in polynomial time, where \(K_{3,3}\) is the Thomsen graph, one of the Kuratowski graphs used to characterize planar graphs. Specifically, we present an O(\(| V|)\)-time algorithm for this problem. This problem was suspected to be NP-complete by \textit{S. Fortune}, \textit{J. Hopcroft} and \textit{J. Wyllie} [ibid. 10, 111-121 (1980; Zbl 0419.05028)]. We also present several pattern graphs for each of which an O(\(| V|)\)-time algorithm exists.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C99
zbMATH DE Number: 3913696
zbMATH Keywords: pattern graph
zbMATH Keywords: Thomsen graph
zbMATH Keywords: Kuratowski graphs
zbMATH Keywords: planar graphs
zbMATH Keywords: algorithm
MaRDI profile type: Publication
full work available at URL: 0304-3975(85)90222-1
OpenAlex ID: W2048838677
cites work: On the computational power of pushdown automata
cites work: Topology of series-parallel networks
cites work: Network Flow and Testing Graph Connectivity
cites work: The directed subgraph homeomorphism problem
cites work: Q4198056
cites work: A note on primitive skew curves
cites work: Parallel concepts in graph theory
cites work: Dividing a Graph into Triconnected Components
cites work: Efficient Planarity Testing
cites work: The NP-completeness column: An ongoing guide
cites work: The subgraph homeomorphism problem
cites work: Q3924253
cites work: A structural characterization of planar combinatorial graphs
cites work: Q3914448
cites work: Q4739657
cites work: Disjoint paths in graphs
cites work: Adjacency in binary matroids
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: Q3886876
cites work: Depth-First Search and Linear Graph Algorithms
cites work: Finding triconnected components of graphs
description: scientific article; zbMATH DE number 3913696