An essential tool for graph generation is surely the ability to draw graphs. There are, of course, many methods for doing so along with many implementations of them. This post describes one more (or perhaps an existing method - I haven't checked).
Firstly, lets divide a graph up into two parts; a) the blocks, also known as 'biconnected components', and b) trees connecting those blocks. This is illustrated in the following set of examples on 6 vertices:
Trees are circled in green, and blocks in red; the vertices in the overlap between two circles are articulation points. Since all trees are planar, a graph need only have planar blocks to be planar overall. The layout then just needs to do a tree layout on the tree bits and some other layout on the embedding of the blocks.
One slight wrinkle is shown by the last example in the image above. There are three parts - two blocks and a tree - just like the one to its left, but sharing a single articulation point. I had assumed (naively) that the blocks and trees were connected together in a kind of 'meta-tree' - which I called the part-tree. Actually, it is possible to have cycles in this part-graph :
This complicates things. Especially since it means the part-graphs themselves can have blocks and trees of their own! In any case, for a large proportion of graphs, this does not matter. Here are drawings for all the planar graphs on 6 vertices:
Where the only real problems remaining look to be for the block embedding/layout of graphs with large numbers of edges. These are the ones on the lower row - with some examples having line crossings.
Firstly, lets divide a graph up into two parts; a) the blocks, also known as 'biconnected components', and b) trees connecting those blocks. This is illustrated in the following set of examples on 6 vertices:
Trees are circled in green, and blocks in red; the vertices in the overlap between two circles are articulation points. Since all trees are planar, a graph need only have planar blocks to be planar overall. The layout then just needs to do a tree layout on the tree bits and some other layout on the embedding of the blocks.
One slight wrinkle is shown by the last example in the image above. There are three parts - two blocks and a tree - just like the one to its left, but sharing a single articulation point. I had assumed (naively) that the blocks and trees were connected together in a kind of 'meta-tree' - which I called the part-tree. Actually, it is possible to have cycles in this part-graph :
This complicates things. Especially since it means the part-graphs themselves can have blocks and trees of their own! In any case, for a large proportion of graphs, this does not matter. Here are drawings for all the planar graphs on 6 vertices:
Where the only real problems remaining look to be for the block embedding/layout of graphs with large numbers of edges. These are the ones on the lower row - with some examples having line crossings.
Comments