Graph embedding: Difference between revisions

Revision as of 08:34, 2 August 2022

Revision as of 18:59, 28 January 2023

Line 56:

==Computational complexity==

The problem of finding the graph genus is [[NP-hard]] (the problem of determining whether an <math>n</math>-vertex graph has genus <math>g</math> is [[NP-complete]]).<ref>{{Citation | last1=Thomassen | first1=Carsten | authorlink = Carsten Thomassen (mathematician) | title=The graph genus problem is NP-complete | year=1989 | journal=Journal of Algorithms | volume=10 | issue = 4 | pages=568–576 | doi = 10.1016/0196-6774(89)90006-0}}</ref>

At the same time, the graph genus problem is [[Fixed-parameter tractability|fixed-parameter tractable]], i.e., [[polynomial time]] algorithms are known to check whether a graph can be embedded into a surface of a given fixed genus as well as to find the embedding.