Skip to main content

Posts

Honeycombs and Macrocyles

Small rings in chemistry are usually laid out as polygons; 5-membered rings as a pentagon, 6-membered as a hexagon, and so on. Once you get beyond about 9-10, this tends to look a little nasty. Or at least, unconventional. So for 'macrocycles', it makes sense to make a less circular, and more wavy outline. Or, to be more exact, there is an inner cycle and several outer cycles, like this: To make it clearer, I have used a chemical-like structure with oxygens in the inner ring. These crown ether s are a particularly clear-cut case, as the ethylene linkages force the particular geometry of the drawing. However, it is not so obvious for other sizes of rings - what possible arrangements are there? Well, it occurred to me today that there is a simple formula for these macrocycle drawings. For a ring of size n with an inner ring of size i and outer rings or size o , you have to have n = (i * o) - i . The formula can be rearranged, but the idea is that you add up all the oute...

Duals and Inner Duals of Planar Graphs

Graphs that can be embedded in the plane are called planar graphs  - that is, they can be drawn without crossings. These drawings (or 'embeddings') have a dual  which also corresponds to a graph, with a vertex in the dual for every face in the original, and an edge in the dual for every pair of faces that share an edge. For example, for each of the embeddings above (in black) of the same graph there is a different dual drawing corresponding to different graphs. If the vertex that represents the outer face is deleted from a dual, you get an inner dual. These inner duals are what Brinkmann et al use for generating fusanes, as I mentioned . The basic idea is to generate the duals, and then expand those into fusanes. Since the (inner) duals necessarily have less vertices than the full graph, this is quite efficient. However, I admit that I couldn't be bothered to implement the algorithm properly, even though the technique is partly based on McKay's method  which I kn...

Generating Trees

Tree generation is a well known (and solved!) problem in computer science. On the other hand, it's pretty important for various problems - in my case, making tree-like fusanes. I'll describe here the slightly tortuous route I took to make trees. Firstly, there is a famous theorem due to Cayley that the number of (labelled) trees on n vertices is n n - 2 which can be proved by using Prüfer sequences . That's all very well, you might well say - but what does all this mean? Well, it's not all that important, since there is a fundamental problem with this approach : the difference between a labelled tree and an unlabelled tree. There are many more labeled trees than unlabeled : There is only one unlabeled tree on 3 vertices, but 3 labeled ones this is easy to check using the two OEIS sequences for this : A000272  (labeled) and A000055  (unlabeled). For n  ranging from 3 to 8 we have [3, 16, 125, 1296, 16807, 262144] labeled trees and [1, 2, 3, 6, 11, 23] ...

Graph Layout

Finally, after much effort, the planar embedder is working. Along the way, a couple of other things have come out of this work : one is an implementation of a fusane generator roughly related to Brinkmann, Caporossi, and Hansen's paper . I say 'roughly' - actually, it is nothing like it! (To be described in a later post.) I now also understand better algorithms for spanning tree generations, and cycle finding. These will also be described in later posts, if necessary. For now, though : what about those planar graphs, eh? Got any images... Fusanes! Or, well, graphs that could model fusanes ( polyhexes ), to be exact. The colors here are vertex equivalence classes, calculated using signatures . These are quite easy examples, however - they are all outerplanar graphs . So what about something more tricky? How about this : Not very nicely laid out, but looks a lot like the top picture here , I think. One lesson I have learnt is that an embedding (which is a combina...

McKay's canonical augmentation method explained for simple graphs

The previous post talked about generating one type of combinatorial object (chessboards) using a method similar to that outlined by Brendan McKay in a paper called " Isomorph-free exhaustive generation " (J Algorithms, 26 (1998) 306-324.). This one will focus instead on simple graphs, which requires both parts of the method. The canonical construction (or canonical augmentation ) method has two components. Firstly, only one 'expansion' of a graph is tried at each step from the set of equivalent expansions. Secondly, the expansions are checked to see if they are the inverse of a 'canonical deletion' for that graph. For an example of the first rule, consider this set of expansions of a 4-vertex graph on the left: Each of the 5-vertex graphs on the right are shown with the newly added vertex and edges in red; the arrows are labelled by the added edge set - so {1:4, 3:4} means edges added from 1 to 4 and 3 to 4. The sets of vertices to add to - {{0}, {1}, {1,3}}...

Generating Chessboards With K-Independant Vertex Sets

After looking at Julio Peironcely's poster on generating chemical structures, where he describes using Canonical Path Augmentation (I think due to Brendan McKay ) I went looking for more about it. One thing I found was this talk/slideshow by Mathieu Dutour Sikirić - incidentally coauthor of a nice book on Chemical Graphs . Anyway; that's the context. Now : about chessboards? Well one of the examples given for augmentation (or 'orderly') schemes of independent vertex sets . I'm not sure what made me think of chessboards for this, but I think it's a fairly standard simple toy example. Let me show an example for 3x3 boards: So, these are all the three by three boards where no two black squares share an edge. In other words, if the board is considered as a grid-shaped graph, then these are the k-independent vertex sets. So the question is : how to generate these? The simple way, of course, is just to fill in every square and eliminate those boards that have pairs ...

Ring Plate Visualisation

One diagram I've often wanted to make was filled-in rings in molecules : Mainly for the purposes of highlighting rings without highlighting the atoms involved. This image was made using the CDK renderbasic module, and a small toy AWTRenderingVisitor that fills in paths. I'm not sure if the current one does this... The gist for the main drawing method is here but is really just stuff seen before. The custom generator for rings is probably more interesting - if very simple - and is here . Note that it doesn't look too nice with inner-ring double bonds: and would look nicer if the double bonds were symmetric. EDIT : Coloring by ring equivalence classes didn't do what I expected... Shouldn't all the outer rings be in the same class? Steran is how I expect, though: