Skip to main content

Posts

Showing posts from 2014

Generating Dungeons With BSP Trees or Sliceable Rectangles

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 labels), and the slicea…

Colorful Expanding Triangulations and Sliceable Rectangular Graphs

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}] and so on…

Misunderstanding Embeddings, and Whitney Flips

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 are subject …

InChI and InChIKey Metadata in Cambridge DSpace Repository (WWMM)

At the end of last year, I updated the metadata on some 175,000 or so items in the Cambridge DSpace repository. These were molecules that made up a copy of the 'WWMM' (the World Wide Molecular Matrix) and they had old 'IChI' identifiers rather than the newer InChI and InChIKey identifiers.
So now - after this update - you can use a search engine to google … er, search for compounds by their InChIKey. For example:
YMSFBKYTOUKHOI-UHFFFAOYSA-N gives just two results, one of which is from PubChem, and the other is Cambridge Repository. Hilariously, the image from PubChem is this:


when the formula is C32H60N4O4. I assume that the connectors in this cycle are just alkane chains, but the layout fails for this kind of 'cyclic lipid peptide' (or whatever it is called!).