EUVIMEDEUVIMED entdecken
Crossref

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

Éric Colin de Verdière, Thomas Magnard

SIAM Journal on Computing · 30.04.2026 · 55 (2) · 410-450

DOI: 10.1137/24m1712400 ↗

Kurz gefasst

Fachartikel in der Zeitschrift SIAM Journal on Computing, online erschienen am 07.04.2026. Verfasst von Éric Colin de Verdière und 1 weiteren Autor:innen. Die Arbeit nennt 49 Literaturangaben. Gefördert von: Agence Nationale de la Recherche.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

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].

Förderung

  • Agence Nationale de la Recherche

Zitieren

APA

Verdière, É. C. D., & Magnard, T. (2026). An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes. SIAM Journal on Computing, 55(2), 410-450. https://doi.org/10.1137/24m1712400

Vancouver

Verdière ÉCD, Magnard T. An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes. SIAM Journal on Computing. 2026;55(2):410-450. doi:10.1137/24m1712400

BibTeX
@article{Verdire2026,
  author = {Verdière, Éric Colin de and Magnard, Thomas},
  title = {An FPT Algorithm for the Embeddability of Graphs Into Two-Dimensional Simplicial Complexes},
  journal = {SIAM Journal on Computing},
  year = {2026},
  volume = {55},
  number = {2},
  pages = {410--450},
  doi = {10.1137/24m1712400}
}
Kostenlos starten →