Deciding whether a grid is a topological subgraph of a planar graph is NP-complete

DOI10.1016/J.DISC.2020.111952zbMATH Open1443.05130OpenAlexW3025791678MaRDI QIDQ5896079FDOQ5896079

Authors: Andrea Jiménez, Tina Janne Schmidt 

Publication date: 8 July 2020

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/11420/4252

Recommendations

• Complexity dichotomy on partial grid recognition
• Complexity of the network median problem on planar grids
• Planar embeddability of the vertices of a graph using a fixed point set is NP-hard
• scientific article; zbMATH DE number 7662167
• Embedding graphs into two-dimensional simplicial complexes

zbMATH Keywords

NP-completenessgridsplanar graphsubdivisionsubgraph homeomorphismtopological subgraph

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10)

Cites Work

• Title not available (Why is that?)
• Graph minors. XIII: The disjoint paths problem
• Title not available (Why is that?)
• Graph minors. V. Excluding a planar graph
• Quickly excluding a planar graph
• Graphs with no 7-wheel subdivision
• Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in \(O(n^{1+\epsilon})\) time
• Structure and recognition of graphs with no 6-wheel subdivision
• The subgraph homeomorphism problem for small wheels
• Finding topological subgraphs is fixed-parameter tractable
• An approach to the subgraph homeomorphism problem
• The subgraph homeomorphism problem
• Optimal binary space partitions in the plane
• Polynomial Bounds for the Grid-Minor Theorem

Cited In (2)

• Complexity dichotomy on partial grid recognition
• Deciding whether a planar graph has a cubic subgraph is NP-complete

This page was built for publication: Deciding whether a grid is a topological subgraph of a planar graph is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5896079)