Friday, August 27, 2010

What can undip codewords code?

Twongs and twogs can make more shapes than the four-letter undip code can code.

A graph must have a Hamilton circuit in order to be undip encoded. (Note that Hamiltonicity is a property of the graph, not the embedding.) That leaves out cubic graphs with self-loops (cubic pseudographs proper) since they can never be Hamiltonian. Only cubic multigraphs can be undip coded.

Furthermore, the embedding must be in the plane (or equivalently the sphere) in order for the coded side bonds to link up predictably. On a higher genus surface, the whole surface area might be encoded in the predictable planar way, but there will remain a closed curve (i.e., the polygon of the plane model, see A Combinatorial Introduction to Topology by Michael Henle) that cannot be seamed across without encountering a surprise.

The photo above shows a digonal prism. Even though a digonal prism is a graph embedded in the sphere, it is not considered a polyhedron by most definitions. For one thing, it contains two-sided faces (digons); for another, it is only 2-edge connected. (Cutting just the two edges shown vertical in the photo would separate the graph into two components.) Note that these are properties of the graph itself, not the embedding. Graphs that are only 1-edge or 2-edge connected make weak structures but they certainly are of sculptural interest. Polyhedron or not, 'udud' codes the digonal prism nicely.

Taking the adjective "plane" to mean "embedded in the plane or sphere," the undip code can encode Hamiltonian plane cubic multigraphs.

No comments: