A paper appeared yesterday on arXiv that I would find very interesting if I believed it to be true: “Characterizing graphs of zonohedra” by Adnan and Hasan. For the purposes of this paper a zonohedron is a centrally symmetric convex polyhedron in which each face is a parallelogram. My understanding is that the graphs of such things (that is, their vertices and edges) are the planar duals of simple line arrangements in the oriented projective plane, while the characterization they claim is equivalent to saying that they are the duals of simple pseudoline arrangements. But the two are not the same, and in fact it's known to be NP-hard to distinguish pseudoline arrangements from line arrangements [Shor, The Victor Klee Festschrift, 1991], making a characterization of the type they claim unlikely.

If a graph is the dual of a pseudoline arrangement but not of a line arrangement, it is still possible to represent it as the skeleton of a polyhedron with parallelogram faces in which some of the dihedral angles are convex and others are flat (exactly π); see my paper on simplicial arrangements for a construction that works equally well for simple arrangements. So I suppose the new paper's characterization could be made to be true by suitably broadening the definition of a convex polyhedron...

I just found this paper: Cubic inflation, mirror graphs, regular maps, and partial cubes, by Brešar, Klavžar, Lipovec, and Mohar. According to it, not much is known about the problem of listing partial cubes in which all vertices have exactly three neighbors — there is one known infinite family (the prisms) and several other sporadic examples, among which is the permutohedron (truncated octahedron). The paper defines an expansion operation for graphs on surfaces (essentially the same as the gem representation from topological graph theory) which, when applied to certain planar graphs, leads to a few more examples.

This immediately made me think about zonohedra, since the truncated octahedron is one. Also, any zonohedron has a skeleton that's dual to a central plane arrangement in three-dimensional space (the arrangement of planes through the origin that are perpendicular to the edges of the zonohedron) and, as with the dual of any affine hyperplane arrangement, it's automatically a partial cube. So I thought I'd go through my catalog of interesting symmetric zonohedra to see whether any of them lead to additional cubic partial cubes.

( Read more... )