Please use this identifier to cite or link to this item:
Publisher DOI: 10.1016/j.entcs.2019.08.048
Title: Deciding Whether a Grid is a Topological Subgraph of a Planar Graph is NP-Complete
Language: English
Authors: Jiménez, Andrea 
Schmidt, Tina Janne 
Keywords: grids; NP-complete; planar graph; subdivision; subgraph homeomorphism; topological subgraph
Issue Date: 2019
Publisher: Elsevier
Source: Electronic Notes in Theoretical Computer Science (346): 545-556 (2019)
Abstract (english): 
The Topological Subgraph Containment (TSC) Problem is to decide, for two given graphs G and H, whether H is a topological subgraph of G. It is known that the TSC Problem is NP-complete when H is part of the input, that it can be solved in polynomial time when H is fixed, and that it is fixed-parameter tractable by the order of H. Motivated by the great significance of grids in graph theory and algorithms due to the Grid-Minor Theorem by Robertson and Seymour, we investigate the computational complexity of the Grid TSC Problem in planar graphs. More precisely, we study the following decision problem: given a positive integer k and a planar graph G, is the k × k grid a topological subgraph of G? We prove that this problem is NP-complete, even when restricted to planar graphs of maximum degree six, via a novel reduction from the Planar Monotone 3-SAT Problem.
Conference: Latin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019 
DOI: 10.15480/882.2552
ISSN: 1571-0661
Journal: Electronic notes in theoretical computer science 
Institute: Mathematik E-10 
Document Type: Chapter/Article (Proceedings)
License: CC BY-NC-ND 4.0 (Attribution-NonCommercial-NoDerivatives) CC BY-NC-ND 4.0 (Attribution-NonCommercial-NoDerivatives)
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
1-s2.0-S1571066119300994-main.pdfVerlags-PDF271,08 kBAdobe PDFView/Open
Show full item record

Page view(s)

Last Week
Last month
checked on Jan 27, 2023


checked on Jan 27, 2023

Google ScholarTM


Note about this record

Cite this record


This item is licensed under a Creative Commons License Creative Commons