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

DOI10.1016/j.entcs.2019.08.048OpenAlexW2978333103WikidataQ113317382 ScholiaQ113317382MaRDI QIDQ5918671

Tina Janne Schmidt, Andrea Jiménez

Publication date: 27 April 2022

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

Full work available at URL: https://doi.org/10.1016/j.entcs.2019.08.048

zbMATH Keywords

subdivisiongridsNP-completeplanar graphsubgraph homeomorphismtopological subgraph

Mathematics Subject Classification ID

Mathematical programming (90Cxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Structure and recognition of graphs with no 6-wheel subdivision
• An approach to the subgraph homeomorphism problem
• The subgraph homeomorphism problem for small wheels
• The subgraph homeomorphism problem
• Graph minors. XIII: The disjoint paths problem
• Graphs with no 7-wheel subdivision
• Optimal Binary Space Partitions in the Plane
• Finding topological subgraphs is fixed-parameter tractable

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