An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912702449844224 |
|---|---|
| author | de Verdière, Éric Colin Magnard, Thomas |
| author_facet | de Verdière, Éric Colin Magnard, Thomas |
| contents | 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. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing an O(2^{poly(c)}.n^2)-time algorithm. If G embeds into C, 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 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, 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 G embeds into C in f(c).O(n) time, for some function f. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2107_06236 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes de Verdière, Éric Colin Magnard, Thomas Computational Geometry 05C85, 57M15 F.2.2; G.2.2 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. We prove that the problem is fixed-parameter tractable in the size of the two-dimensional complex, by providing an O(2^{poly(c)}.n^2)-time algorithm. If G embeds into C, 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 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, 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 G embeds into C in f(c).O(n) time, for some function f. |
| title | An FPT algorithm for the embeddability of graphs into two-dimensional simplicial complexes |
| topic | Computational Geometry 05C85, 57M15 F.2.2; G.2.2 |
| url | https://arxiv.org/abs/2107.06236 |