Please use this identifier to cite or link to this item:
https://doi.org/10.15480/882.2552
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 | URI: | http://hdl.handle.net/11420/4252 | 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: | ![]() |
Appears in Collections: | Publications with fulltext |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
1-s2.0-S1571066119300994-main.pdf | Verlags-PDF | 271,08 kB | Adobe PDF | View/Open![]() |
Page view(s)
370
Last Week
1
1
Last month
7
7
checked on Jan 27, 2023
Download(s)
245
checked on Jan 27, 2023
Google ScholarTM
Check
Note about this record
Cite this record
Export
This item is licensed under a Creative Commons License