An Approach to the Subgraph Homeomorphism Problem

Abstract 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 Fortune, Hopcroft and Wyllie (1980). We also present several pattern graphs for each of which an O(| V |)-time algorithm exists.

• Publication year

  1985

• Venue

  Theoretical Computer Science

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0304-3975(85)90222-1
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Disjoint paths in graphs

  2006cited by this paper
• Adjacency in Binary Matroids

  1986cited by this paper
• Finding triconnected components of graphs

  1983cited by this paper
• Edge-deletion and edge-contraction problems

  1982cited by this paper
• Combinatorial Optimization: Algorithms and Complexity

  1981cited by this paper
• The two disjoint path problem and wire routing design

  1980cited by this paper
• A Polynomial Solution to the Undirected Two Paths Problem

  1980cited by this paper
• The Directed Subgraph Homeomorphism Problem

  1978cited by this paper
• The subgraph homeomorphism problem

  1978cited by this paper
• Network Flow and Testing Graph Connectivity

  1975cited by this paper
• The Design and Analysis of Computer Algorithms

  1974cited by this paper
• Efficient Planarity Testing

  1974cited by this paper
• Dividing a Graph into Triconnected Components

  1973cited by this paper
• Depth-First Search and Linear Graph Algorithms

  1972cited by this paper
• Graph theory

  1969cited by this paper
• Topology of series-parallel networks

  1965cited by this paper
• A note on primitive skew curves

  1943cited by this paper
• A structural characterization of planar combinatorial graphs

  1937cited by this paper
• Sur le problème des courbes gauches en Topologie

  year unknowncited by this paper

• 2D Minimal Graph Rigidity is in NC for One-Crossing-Minor-Free Graphs

  2025influential citation
• Revising the Fellows-Kaschube $K_{3, 3}$ Search

  2021cites this paper
• Deciding Whether a Grid is a Topological Subgraph of a Planar Graph is NP-Complete

  2019cites this paper
• NC Algorithms for Computing a Perfect Matching, the Number of Perfect Matchings, and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2019cites this paper
• NC Algorithms for Perfect Matching and Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• A Large Set of Torus Obstructions and How They Were Discovered

  2018cites this paper
• NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs

  2018cites this paper
• The simple, little and slow things count: on parameterized counting complexity

  2015cites this paper
• Connectivity Preserving Iterative Compaction and Finding 2 Disjoint Rooted Paths in Linear Time

  2015cites this paper
• Reachability in K3,3-free and K5-free Graphs is in Unambiguous Logspace

  2014cites this paper
• Derandomizing Isolation Lemma for $K_{3, 3}$-free and $K_5$-free Bipartite Graphs

  2014cites this paper
• Counting perfect matchings in graphs that exclude a single-crossing minor

  2014cites this paper
• On the complexity of isomorphism testing for restricted classes of graphs

  2010cites this paper
• Some Tractable Win-Lose Games

  2010cites this paper
• Structure and Recognition of Graphs with No 6-wheel Subdivision

  2009cites this paper
• A minimization version of a directed subgraph homeomorphism problem

  2009cites this paper
• Reachability in K3, 3-Free Graphs and K5-Free Graphs Is in Unambiguous Log-Space

  2009influential citation
• Graph Isomorphism for K_{3, 3}-free and K_5-free graphs is in Log-space

  2009cites this paper
• The Bidimensionality Theory and Its Algorithmic Applications

  2008influential citation
• A semidefinite programming approach to the graph realization problem : theory, applications and extensions

  2007cites this paper
• Almost Exact Matchings

  2007cites this paper
• The structure of K3, 3-subdivision-free toroidal graphs

  2007cites this paper
• A Simpler and Faster Torus Embedding Algorithm

  2006cites this paper
• A semidefinite programming approach to tensegrity theory and realizability of graphs

  2006cites this paper
• A faster algorithm for torus embedding

  2006cites this paper
• Exponential Speedup of Fixed-Parameter Algorithms for Classes of Graphs Excluding Single-Crossing Graphs as Minors

  2005cites this paper
• Descriptive complexity of modularity problems on graphs

  2005cites this paper
• Forbidden minors and subdivisions for toroidal graphs with no K3, 3's

  2005cites this paper
• The structure and labelled enumeration of $K\sb 3,3$-subdivision-free projective-planar graphs

  2004influential citation
• The obstructions for toroidal graphs with no K3, 3's

  2004cites this paper
• Counting labelled projective-planar graphs without a K_{3,3}-subdivision

  2004cites this paper
• Approximation algorithms for classes of graphs excluding single-crossing graphs as minors

  2004cites this paper
• Characterization and enumeration of toroidal K_{3,3}-subdivision-free graphs

  2004cites this paper
• Tight upper bound on the number of edges in a bipartite K3, 3-free or K5-free graph with an application

  2002cites this paper
• -Approximation for Treewidth of Graphs Excluding a Graph with One Crossing as a Minor

  2002cites this paper
• Exponential Speedup of Fixed-Parameter Algorithms on K3, 3-Minor-Free or K5-Minor-Free Graphs

  2002cites this paper
• Exact algorithms for NP hard problems on networks: design, analysis and implementation

  2002cites this paper
• Fast approximation schemes for K3, 3-minor-free or K5-minor-free graphs

  2001cites this paper
• Quantum Molecular Similarity: Theory and Applications to the Evaluation of Molecular Properties, Biological Activities and Toxicity

  2001cites this paper
• Algorithms for Graphs of (Locally) Bounded Treewidth

  2001cites this paper
• Efficient Algorithms for Acyclic Colorings of Graphs

  1999cites this paper
• Efficient Approximation Schemes for Maximization Problems on K3,3-free or K5-free Graphs

  1998cites this paper
• Practical Approximation Schemes for Maximum Induced-Subgraph Problems on K_{3, 3}-free or K_5-free Graphs

  1996cites this paper
• Sequential and Parallel Approximation of Maximum Induced-Subgraph Problems on Sparse Graphs

  1996cites this paper
• Practical PTAS for Maximum Induced-Subgraph Problems on $K_{3,3}$-free of $K_5$-free Graphs

  1996cites this paper
• Parallel Complexity of Partitioning a Planar Graph Into Vertex-induced Forests

  1996cites this paper
• NC Algorithms for Partitioning Sparse Graphs into Induced Forests with an Application

  1995cites this paper
• NC Algorithms for Partitioning Planar Graphs into Induced Forests and Approximating NP-Hard Problems

  1995cites this paper
• Parallel Algorithms for Maximal Acyclic Sets

  1995cites this paper
• On a conjecture of Tuza about packing and covering of triangles

  1995cites this paper
• A Parallel Algorithm for Finding a Triconnected Component Separator with an Application

  1994cites this paper
• Sequential and parallel algorithms to find a K5 minor

  1992cites this paper
• Sequential and parallel algorithms to find a K 5 minor

  1992cites this paper
• Searching for K 3,3in linear time

  1991cites this paper
• Efficient processing of hierarchical graphs

  1990cites this paper
• Parallel Algorithms for the Subgraph Homeomorphism Problem

  1989cites this paper
• Efficient parallel algorithms for testing connectivity and finding disjoint s-t paths in graphs

  1989cites this paper
• Processor efficient parallel algorithms for the two disjoint paths problem, and for finding a Kuratowski homeomorph

  1989cites this paper
• On Parallel Complexity of the Subgraph Homeomorphism and the Subgraph Isomorphism Problem for Classes of Planar Graphs

  1989cites this paper
• NC Algorithms for Computing the Number of Perfect Matchings in K_3,3-Free Graphs and Related Problems

  1989cites this paper
• Matchings and covers in hypergraphs

  1988cites this paper
• NC Algorithms for Computing the Number of Perfect Matchings in K3, 3-free Graphs and Related Problems

  1988cites this paper
• Extending Planar Graph Algorithms to K_3,3-Free Graphs

  1988cites this paper
• Fast Parallel Algorithms for the Subgraph Homophormism and the Subgraph Isomorphism Problem for Classes of Planat Graphs

  1987influential citation
• Journal of Graph Algorithms and Applications Subgraph Homeomorphism via the Edge Addition Planarity Algorithm

  year unknowncites this paper
• Journal of Graph Algorithms and Applications Flows in One-crossing-minor-free Graphs 202 Chambers and Eppstein Flows in One-crossing-minor-free Graphs

  year unknowncites this paper