Publisher DOI: 10.1016/j.disc.2020.111952
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: Sep-2020
Source: Discrete Mathematics 9 (343): 111952 (2020-09)
Abstract (english): 
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.
ISSN: 0012-365X
Journal: Discrete mathematics 
Institute: Mathematik E-10 
Document Type: Article
Appears in Collections:Publications without fulltext

Show full item record

Page view(s)

Last Week
Last month
checked on Jul 5, 2022

Google ScholarTM


Add Files to Item

Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.