Some Stuff

So, I admit that the original reason for looking at sliceable rectangles  was because of this gaming stackoverflow  question about generating dungeon maps. The approach described there uses something called a binary split partition tree ( BSP Tree ) that's usually used in the context of 3D - notably in the rendering engine of the game Doom . Here is a BSP tree, as an example: In the image, we have a sliced rectangle on the left, with the final rectangles labelled with letters (A-E) and the slices with numbers (1-4). The corresponding tree is on the right, with the slices as internal nodes labelled with 'h' for horizontal and 'v' for vertical. Naturally, only the leaves correspond to rectangles, and each internal node has two children - it's a binary tree. So what is the connection between such trees and the sliceable dual graphs? Well, the rectangles are related in exactly the expected way: Here, the same BSP tree is on the left (without some label...

There is a whole area of study on visualisations called cartograms - most appealing are the ones that make countries look like inflated or deflated balloons . The rectangular versions of these are less pretty, but more interesting to me from a graph theory perspective. I came across this subject via an impressive masters thesis  by Vincent Kusters : ' Characterizing Graphs with a Sliceable Rectangular Dual' … which is a title that will take some explaining. Firstly, what is a 'rectangular dual' when it's at home? Well check this out: Clearly the thing on the left is a graph, and on the right is its rectangular dual - in fact, this is the smallest 'sliceable' dual. By sliceable, I mean that the white rectangles can be made by recursively slicing up a rectangle. For example, if a slice is like [{0, 3, 4, 5, 6}, {1, 2}] for making the first split into the areas of 1 and 2 on the right, and all the rest on the left. The next could be [{0}, {3, 4, 5, 6...

So I should correct something that I posted a while ago  about embedding 3-connected graphs. The most obvious examples of this class of graph are polyhedra  - tetrahedra, cubes, etc - and maybe it's obvious that there is only one  way to embed these in the plane. So in that sense, 'enumerating' the embeddings for these graphs is quite easy ... there's just one to count. Of course, this embedding can be drawn with any of its cycles as an outer face; this is what gave rise to the different looking drawings. I guess the way to think about it is that the embedding is on the surface of a sphere - where there is no 'privileged' face to call the outer  face - and that the drawing on the plane just picks one of the faces to 'squash flat' as I put it back in (wow) 2011. Anyway - on to Whitney flips! There are a class of graphs that can be embedded in the plane in different ways (that is, the combinatorial map is different for the same outer face). These ...