Computational Complexity
The problem of finding the graph genus is NP-hard (the problem of determining whether an n-vertex graph has genus g is NP-complete).
At the same time, the graph genus problem is 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.
The first breakthrough in this respect happened in 1979, when algorithms of time complexity O(nO(g)) were independently submitted to the Annual ACM Symposium on Theory of Computing: one by I. Filotti and G.L. Miller and another one by John Reif. Their approaches were quite different, but upon the suggestion of the program committee they presented a joint paper.
In 1999 it was reported that the fixed-genus case can be solved in time linear in the graph size and doubly exponential in the genus.
Read more about this topic: Graph Embedding
Famous quotes containing the word complexity:
“The price we pay for the complexity of life is too high. When you think of all the effort you have to put in—telephonic, technological and relational—to alter even the slightest bit of behaviour in this strange world we call social life, you are left pining for the straightforwardness of primitive peoples and their physical work.”
—Jean Baudrillard (b. 1929)