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)
Journal or Series Name: Electronic notes in theoretical computer science 
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.
DOI: 10.15480/882.2552
ISSN: 1571-0661
Institute: Mathematik E-10 
Type: InProceedings (Aufsatz / Paper einer Konferenz etc.)
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 PDFThumbnail
Show full item record

Page view(s)

Last Week
Last month
checked on Nov 28, 2020


checked on Nov 28, 2020

Google ScholarTM


Note about this record


This item is licensed under a Creative Commons License Creative Commons