An approach to the subgraph homeomorphism problem

DOI10.1016/0304-3975(85)90222-1zbMath0572.68052OpenAlexW2048838677MaRDI QIDQ1062457

Takao Asano

Publication date: 1985

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(85)90222-1

zbMATH Keywords

algorithmplanar graphsKuratowski graphspattern graphThomsen graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph theory (05C99)

Related Items

Approximation algorithms for classes of graphs excluding single-crossing graphs as minors ⋮ A parallel algorithm for finding a triconnected component separator with an application ⋮ Searching forK_3,3in linear time ⋮ On a conjecture of Tuza about packing and covering of triangles ⋮ NC algorithms for computing the number of perfect matchings in \(K_{3,3}\)-free graphs and related problems ⋮ Revising the Fellows-Kaschube $K_{3,3}$ Search ⋮ Parallel complexity of partitioning a planar graph into vertex-induced forests ⋮ NC algorithms for partitioning planar graphs into induced forests and approximating NP-hard problems ⋮ Almost exact matchings ⋮ A large set of torus obstructions and how they were discovered ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Efficient algorithms for acyclic colorings of graphs ⋮ The structure of \(K_{3,3}\)-subdivision-free toroidal graphs ⋮ Some Tractable Win-Lose Games ⋮ Deciding whether a grid is a topological subgraph of a planar graph is NP-complete ⋮ Extending planar graph algorithms to \(K_{3,3}\)-free graphs ⋮ A minimization version of a directed subgraph homeomorphism problem ⋮ On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs ⋮ The obstructions for toroidal graphs with no \(K_{3,3}\)'s ⋮ Structure and recognition of graphs with no 6-wheel subdivision ⋮ NC Algorithms for Computing a Perfect Matching and a Maximum Flow in One-Crossing-Minor-Free Graphs ⋮ Tight upper bound on the number of edges in a bipartite \(K_{3,3}\)-free or \(K_{5}\)-free graph with an application. ⋮ Forbidden minors and subdivisions for toroidal graphs with no K3,3's

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Adjacency in binary matroids
• The directed subgraph homeomorphism problem
• The subgraph homeomorphism problem
• Disjoint paths in graphs
• Parallel concepts in graph theory
• Topology of series-parallel networks
• On the computational power of pushdown automata
• A structural characterization of planar combinatorial graphs
• Finding triconnected components of graphs
• A Polynomial Solution to the Undirected Two Paths Problem
• Efficient Planarity Testing
• Network Flow and Testing Graph Connectivity
• Dividing a Graph into Triconnected Components
• Depth-First Search and Linear Graph Algorithms
• A note on primitive skew curves
• The NP-completeness column: An ongoing guide