###### Options

# Deciding Whether a Grid is a Topological Subgraph of a Planar Graph is NP-Complete

Citation Link: https://doi.org/10.15480/882.2552

Publikationstyp

Conference Paper

Publikationsdatum

2019

Sprache

English

Institut

TORE-URI

Enthalten in

Volume

346

Start Page

545

End Page

556

Citation

Electronic Notes in Theoretical Computer Science (346): 545-556 (2019)

Contribution to Conference

Publisher DOI

Scopus ID

Publisher

Elsevier

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.

Schlagworte

grids

NP-complete

planar graph

subdivision

subgraph homeomorphism

topological subgraph

DDC Class

510: Mathematik

Loading...

**Name**

1-s2.0-S1571066119300994-main.pdf

**Size**

271.08 KB

**Format**

Adobe PDF