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 combinatorial object) is not at all like a drawing (which is a geometric object). the embedding only tells you which vertices are part of which face, while the drawing has actual 2D coordinates.
There is an implementation of Plestenjak's spring layout algorithm - but I must have messed up somewhere, as it doesn't work so well. Take a look at this 'before and after' image of fullerene-26 :
It's a bit hard to see at this size, but the one on the left is the 'before' picture, where no refinement of the coordinates has been performed, and the one on the right has been refined. Well 'coarsened' in some places - notably the vertex at the top, which happens to be the central one.
Code for this is here.
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 :
There is an implementation of Plestenjak's spring layout algorithm - but I must have messed up somewhere, as it doesn't work so well. Take a look at this 'before and after' image of fullerene-26 :
Code for this is here.
Comments