Planarity is a rather addictive game developed by John Tantalo. The idea is that you're given a planar graph, drawn with lots of crossings, and your goal is to move vertices around so as to recover a planar embedding. The game can get surprisingly challenging, and has even spawned a photoshop tribute called, 'Planarity, My Anti-drug'.
If we put on our theory hats, the first question that pops out is: how many vertices might you need to move in order to move from an embedding of a planar graph to a planar embedding ? This process, of moving vertices around to remove crossings, is called untangling. Technically, H is an untangling of G if H is crossing free and is isomorphic as G (in other words, untangling might allow more general moves than the sliding allowed by Planarity). A vertex of G was said to be fixed if it was mapped (by the isomorphism) to a vertex of H with the same coordinates.
Back in 1998, it was first asked whether a graph could be made planar while keeping a constant fraction of vertices fixed. The answer, shown by Pach and Tardos, was no, via a graph in which at most roughly n^{2/3} of the vertices could stay fixed (which is one way of explaining the difficulty of Planarity). Of course, the next question was whether it was the case that all planar graphs could be untangled by fixing at least some n^epsilon vertices.
A recent paper by Bose, Dujmovic, Hurtado, Langerman, Morin and Wood answers this question in the affirmative, showing that any geometric planar graph can be untangled while keeping at least n^{1/4} vertices fixed. The proofs involved are intricate, but are graph-theoretic and "elementary" in nature.
How long did I sleep last night?
ReplyDelete"Acknowledgements
This research was initiated at the Bellairs Workshop on Computational Geometry for Geometric Reconfigura-
tions, February 1st to 9th, 2009. The authors are grateful to Godfried Toussaint for organizing the workshop and to the other workshop participants for providing a stimulating working environment.
"
For me, the striking thing about this game was how successful one can be following a simple greedy/clustering strategy with occasional backtracking. Is there a general result on planar graphs to be squeezed out of this? Or does it have more to do with the particular input distribution used?
ReplyDeleteI just found this article, thus, the game begins. I have found a new drug.
ReplyDeleteThere is an enormous difference between the planarity game and the untangling problem studied by Bose et al. In the planarity game, one cannot move a vertex beyond the boundary of the screen. In the untangling problem there is no such bounding box. Start playing the game, and you will see this is a severe limitation.
ReplyDeleteAlso ... there was a version of planarity for macs in 1989! I played it as part of my first year math course at university.
D.R.W.