DROPS

Document

DOI: 10.4230/LIPIcs.ESA.2021.32

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

Authors: Éric Colin de Verdière and Thomas Magnard

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract

We consider the embeddability problem of a graph G into a two-dimensional simplicial complex C: Given G and C, decide whether G admits a topological embedding into C. The problem is NP-hard, even in the restricted case where C is homeomorphic to a surface. It is known that the problem admits an algorithm with running time f(c)n^{O(c)}, where n is the size of the graph G and c is the size of the two-dimensional complex C. In other words, that algorithm is polynomial when C is fixed, but the degree of the polynomial depends on C. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing a deterministic f(c)n³-time algorithm. We also provide a randomized algorithm with expected running time 2^{c^{O(1)}}n^{O(1)}. Our approach is to reduce to the case where G 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; the only elaborated tool that we use is an algorithm to compute grid minors.

Cite as

Éric Colin de Verdière and Thomas Magnard. An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2021.32,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Magnard, Thomas},
  title =	{{An FPT Algorithm for the Embeddability of Graphs into Two-Dimensional Simplicial Complexes}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{32:1--32:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.32},
  URN =		{urn:nbn:de:0030-drops-146139},
  doi =		{10.4230/LIPIcs.ESA.2021.32},
  annote =	{Keywords: computational topology, embedding, simplicial complex, graph, surface, fixed-parameter tractability}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2018.27

Embedding Graphs into Two-Dimensional Simplicial Complexes

Authors: Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

We consider the problem of deciding whether an input graph G admits a topological embedding into a two-dimensional simplicial complex C. This problem includes, among others, the embeddability problem of a graph on a surface and the topological crossing number of a graph, but is more general. The problem is NP-complete when C is part of the input, and we give a polynomial-time algorithm if the complex C is fixed. Our strategy is to reduce the problem to an embedding extension problem on a surface, which has the following form: Given a subgraph H' of a graph G', and an embedding of H' on a surface S, can that embedding be extended to an embedding of G' on S? Such problems can be solved, in turn, using a key component in Mohar's algorithm to decide the embeddability of a graph on a fixed surface (STOC 1996, SIAM J. Discr. Math. 1999).

Cite as

Éric Colin de Verdière, Thomas Magnard, and Bojan Mohar. Embedding Graphs into Two-Dimensional Simplicial Complexes. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{verdiere_et_al:LIPIcs.SoCG.2018.27,
  author =	{Verdi\`{e}re, \'{E}ric Colin de and Magnard, Thomas and Mohar, Bojan},
  title =	{{Embedding Graphs into Two-Dimensional Simplicial Complexes}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{27:1--27:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.27},
  URN =		{urn:nbn:de:0030-drops-87401},
  doi =		{10.4230/LIPIcs.SoCG.2018.27},
  annote =	{Keywords: computational topology, embedding, simplicial complex, graph, surface}
}

Search Results

Documents authored by Magnard, Thomas

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

Abstract

Cite as

Embedding Graphs into Two-Dimensional Simplicial Complexes

Abstract

Cite as

Thanks for your feedback!

Could not send message