On stating the obvious

I've been working on a new Wikipedia article on circular layouts in graph drawing, and I wanted to say something in it about Planarity, a puzzle that involves moving the vertices of a graph drawing around, starting from a circular layout, to show that the graph is planar. However, despite the existence of quite a bit of academic work that explicitly states that it's inspired by Planarity, I couldn't find any published source that describes the initial layout of the puzzle.

Oleg Verbitsky's paper "On the obfuscation complexity of planar graphs" (Theor. Comput. Sci. 2008 and arXiv:0705.3748) says in the first sentence of the abstract that it's motivated by Planarity. The paper proves that a randomly permuted circular layout (like the one used as the initial state in Planarity) approximates the maximum possible number of crossings to within an approximation ratio of three, in expectation. But it doesn't actually say that Planarity uses this kind of layout, or conclude from its theoretical results that this kind of layout is a good choice for this puzzle.

Several authors have been studied the problem of planarizing a nonplanar layout by moving as few vertices as possible, and (although the problem predates the Planarity game) the paper on this problem by Goaoc et al. 2009 mentions Planarity, and mentions results involving initial vertex sets in convex position, but does not mention that this is the initial position of Planarity.

"Perceptual organization in user-generated graph layouts", by van Ham and Rogowitz in IEEE TVCG 2008, studied user experiences with perceptual tasks in graph visualization within an interactive environment inspired by and similar to the game play in Planarity. They compare how well the users were able to rearrange the graphs and perform their set tasks for several different starting layouts, one of which is the randomized circular layout of Planarity. Unsurprisingly, they find that using this deliberately-tangled layout slows the users down. But they don't say that this layout is the one used by Planarity.

"Comparing Multi-Touch Tabletops and Multi-Mouse SingleDisplay Groupware Setups (Hansen and Hourcade, MexIHC'10) comes very close to what I want: in a paragraph that begins "inspired by Planarity" they write about a task of "untangling a ring graph with randomly placed vertices". But I think here "ring" may be a description of the network connectivity rather than the initial placement, and in any case again they don't say how similar or different their system is to planarity.

There are also mainstream media sources for Planarity itself, but I didn't find any descriptions of its initial configuration there, either. And the Planarity site goes into great detail about how it generates its graphs but says nothing about how they are placed into the initial configuration.

In the absence of good enough sources for the circularity of its layouts, I ended up mentioning Planarity in a see-also link of the circular layout article, rather than actually including it in the main text of the article. It's obvious to anyone who spends any amount of time playing Planarity that its initial layout is circular. But sometimes, being obvious isn't enough: you have to say it.

---

Comments: