Related Theoretical Research
The problem of determining whether a graph is planar can be solved in linear time with a simple algorithm, and any such graph is guaranteed to have a straight-line embedding by Fáry's theorem, that can also be found from the planar embedding in linear time. Therefore, any puzzle could be solved in linear time by a computer. However, these puzzles are not as straightforward for human players to solve.
In the field of computational geometry, the process of moving a subset of the vertices in a graph embedding to eliminate edge crossings has been studied by Pach and Tardos (2002), and others, inspired by the planarity puzzle. The results of these researchers shows that (in theory, assuming that the field of play is the infinite plane rather than a bounded rectangle) it is always possible to solve the puzzle while leaving of the input vertices fixed in place at their original positions, for a constant that has not been determined precisely but lies between 1/4 and 1/2. When the planar graph to be untangled is a cycle graph, a larger number of vertices may be fixed in place. However, determining the largest number of vertices that may be left in place for a particular input puzzle (or equivalently, the smallest number of moves needed to solve the puzzle) is NP-complete.
Verbitsky (2008) has shown that the randomized circular layout used for the initial state of Planarity is nearly the worst possible in terms of its number of crossings: regardless of what planar graph is to be tangled, the expected value of the number of crossings for this layout is within a factor of three of the largest number of crossings among all layouts.
Read more about this topic: Planarity
Famous quotes containing the words related, theoretical and/or research:
“In the middle years of childhood, it is more important to keep alive and glowing the interest in finding out and to support this interest with skills and techniques related to the process of finding out than to specify any particular piece of subject matter as inviolate.”
—Dorothy H. Cohen (20th century)
“The hypothesis I wish to advance is that ... the language of morality is in ... grave disorder.... What we possess, if this is true, are the fragments of a conceptual scheme, parts of which now lack those contexts from which their significance derived. We possess indeed simulacra of morality, we continue to use many of the key expressions. But we have—very largely if not entirely—lost our comprehension, both theoretical and practical, of morality.”
—Alasdair Chalmers MacIntyre (b. 1929)
“Our science has become terrible, our research dangerous, our findings deadly. We physicists have to make peace with reality. Reality is not as strong as we are. We will ruin reality.”
—Friedrich Dürrenmatt (1921–1990)