Verlagslink DOI: 10.1016/j.disc.2020.111952
Titel: Deciding whether a grid is a topological subgraph of a planar graph is NP-complete
Sprache: Englisch
Autor/Autorin: Jiménez, Andrea 
Schmidt, Tina Janne 
Schlagwörter: Grids; NP-complete; Planar graph; Subdivision; Subgraph homeomorphism; Topological subgraph
Erscheinungs­datum: Sep-2020
Quellenangabe: Discrete Mathematics 9 (343): 111952 (2020-09)
Zusammenfassung (englisch): 
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.
URI: http://hdl.handle.net/11420/6174
ISSN: 0012-365X
Zeitschrift: Discrete mathematics 
Institut: Mathematik E-10 
Dokumenttyp: Artikel/Aufsatz
Enthalten in den Sammlungen:Publications without fulltext

Zur Langanzeige

Seitenansichten

93
Letzte Woche
1
Letzten Monat
1
checked on 01.10.2022

Google ScholarTM

Prüfe

Volltext ergänzen

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.