Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2552
DC FieldValueLanguage
dc.contributor.authorJiménez, Andrea-
dc.contributor.authorSchmidt, Tina Janne-
dc.date.accessioned2020-01-03T09:16:00Z-
dc.date.available2020-01-03T09:16:00Z-
dc.date.issued2019-
dc.identifier.citationElectronic Notes in Theoretical Computer Science (346): 545-556 (2019)de_DE
dc.identifier.issn1571-0661de_DE
dc.identifier.urihttp://hdl.handle.net/11420/4252-
dc.description.abstractThe 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.en
dc.language.isoende_DE
dc.publisherElsevierde_DE
dc.relation.ispartofElectronic notes in theoretical computer sciencede_DE
dc.rightsCC BY-NC-ND 4.0de_DE
dc.rights.urihttps://creativecommons.org/licenses/by-nc-nd/4.0/
dc.subjectgridsde_DE
dc.subjectNP-completede_DE
dc.subjectplanar graphde_DE
dc.subjectsubdivisionde_DE
dc.subjectsubgraph homeomorphismde_DE
dc.subjecttopological subgraphde_DE
dc.subject.ddc510: Mathematikde_DE
dc.titleDeciding Whether a Grid is a Topological Subgraph of a Planar Graph is NP-Completede_DE
dc.typeinProceedingsde_DE
dc.identifier.doi10.15480/882.2552-
dc.type.dinicontributionToPeriodical-
dcterms.DCMITypeText-
tuhh.identifier.urnurn:nbn:de:gbv:830-882.060692-
tuhh.oai.showtruede_DE
tuhh.abstract.englishThe 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.de_DE
tuhh.publisher.doi10.1016/j.entcs.2019.08.048-
tuhh.publication.instituteMathematik E-10de_DE
tuhh.identifier.doi10.15480/882.2552-
tuhh.type.opusInProceedings (Aufsatz / Paper einer Konferenz etc.)-
dc.type.drivercontributionToPeriodical-
dc.type.casraiConference Paper-
tuhh.container.volume346de_DE
tuhh.container.startpage545de_DE
tuhh.container.endpage556de_DE
dc.relation.conferenceLatin and American Algorithms, Graphs and Optimization Symposium, LAGOS 2019de_DE
dc.rights.nationallicensefalsede_DE
dc.identifier.scopus2-s2.0-85076258754-
local.status.inpressfalsede_DE
datacite.resourceTypeConference Paper-
datacite.resourceTypeGeneralText-
item.grantfulltextopen-
item.cerifentitytypePublications-
item.openairetypeinProceedings-
item.creatorOrcidJiménez, Andrea-
item.creatorOrcidSchmidt, Tina Janne-
item.languageiso639-1en-
item.creatorGNDJiménez, Andrea-
item.creatorGNDSchmidt, Tina Janne-
item.fulltextWith Fulltext-
item.openairecristypehttp://purl.org/coar/resource_type/c_5794-
item.mappedtypeinProceedings-
crisitem.author.deptMathematik E-10-
crisitem.author.parentorgStudiendekanat Elektrotechnik, Informatik und Mathematik (E)-
Appears in Collections:Publications with fulltext
Files in This Item:
File Description SizeFormat
1-s2.0-S1571066119300994-main.pdfVerlags-PDF271,08 kBAdobe PDFView/Open
Thumbnail
Show simple item record

Page view(s)

361
Last Week
1
Last month
7
checked on Dec 6, 2022

Download(s)

221
checked on Dec 6, 2022

Google ScholarTM

Check

Note about this record

Cite this record

Export

This item is licensed under a Creative Commons License Creative Commons