Verlagslink DOI: 10.1016/j.entcs.2019.08.048
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: 2019
Verlag: Elsevier
Quellenangabe: Electronic Notes in Theoretical Computer Science (346): 545-556 (2019)
Zusammenfassung (englisch): 
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.
Konferenz: 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
Zeitschrift: Electronic notes in theoretical computer science 
Institut: Mathematik E-10 
Dokumenttyp: Kapitel (Konferenzband)
Lizenz: CC BY-NC-ND 4.0 (Attribution-NonCommercial-NoDerivatives) CC BY-NC-ND 4.0 (Attribution-NonCommercial-NoDerivatives)
Enthalten in den Sammlungen:Publications with fulltext

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat
1-s2.0-S1571066119300994-main.pdfVerlags-PDF271,08 kBAdobe PDFÖffnen/Anzeigen
Miniaturbild
Zur Langanzeige

Seitenansichten

342
Letzte Woche
1
Letzten Monat
7
checked on 06.10.2022

Download(s)

214
checked on 06.10.2022

Google ScholarTM

Prüfe

Feedback zu diesem Datensatz

Diesen Datensatz zitieren

Export

Diese Ressource wurde unter folgender Copyright-Bestimmung veröffentlicht: Lizenz von Creative Commons Creative Commons