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

DOI10.1016/J.DISC.2020.111952MaRDI QIDQ5896079zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

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

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)