An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes

Abstract. We consider the embeddability problem of a graph [Formula: see text] into a two-dimensional simplicial complex [Formula: see text]: Given [Formula: see text] and [Formula: see text], decide whether [Formula: see text] admits a topological embedding into [Formula: see text]. The problem is NP-hard, even in the restricted case where [Formula: see text] is homeomorphic to a surface. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing an [Formula: see text]-time algorithm. If [Formula: see text] embeds into [Formula: see text], we can compute a representation of an embedding in the same amount of time. Moreover, we show that several known problems reduce to this one, such as the crossing number and the planarity number problems, and, under some conditions, the embedding extension problem. Our approach is to reduce to the case where [Formula: see text] has bounded branchwidth via an irrelevant vertex method, and to apply dynamic programming. We do not rely on any component of the existing linear-time algorithms for embedding graphs on a fixed surface, but only on algorithms from graph minor theory. However, by combining our results with a linear-time algorithm for embedding graphs on surfaces and with a very recent result for the irrelevant vertex method, we can decide whether [Formula: see text] embeds into [Formula: see text] in [Formula: see text] time, for some function [Formula: see text].