Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering

DOI10.1137/19M1262504MaRDI QIDQ5885586

Marcin Pilipczuk, Fedor V. Fomin, Saket Saurabh, Michał Pilipczuk, Daniel Lokshtanov, Dániel Marx

Publication date: 4 April 2023

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1604.05999

zbMATH Keywords

planar graphs; treewidth; subgraph isomorphism; parameterized complexity; subexponential algorithms

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C10: Planar graphs; geometric and topological aspects of graph theory

05C75: Structural characterization of families of graphs

05C85: Graph algorithms (graph-theoretic aspects)