2
$\begingroup$

Can anyone point me to a gallery (printed or online) of unlabelled trees, sorted according to their order (i.e., number of vertices)? That is, for each order n in oeis.org/A000055 (up to maybe n=11 or so) I'd like to see a visualization of all the trees.

I found Gary Fredericks' online database Small Simple Graphs but there are a few problems which make it unsuitable for my purposes: 1) It's for graphs in general as opposed to trees. (Though maybe there is some way of using the filters in this tool to suppress the graphs with cycles?) 2) It works only for n up to 9. 3) It shows only five graphs at a time, though I'd like to see all the trees for a given n on the same web page (or printed page).

Alternatively can someone point me to some code which can automatically generate images of such trees, preferably in a vector format? Then I could arrange them myself into a single web page or LaTeX document.

$\endgroup$
  • $\begingroup$ Regarding the database you link: a better source (fully downloadable) is here. I'm mentioning this only because Google brought me here when looking for a database of small graphs (not trees). $\endgroup$ – Szabolcs Sep 26 '14 at 13:53
3
$\begingroup$

geng which comes with nauty can generate these trees (along with other classes of graphs) very quickly; they can be viewed with showg. It will give a list of adjacencies and it's straightforward to write one's own script to convert it to one's desired format. The command is e.g.

geng 7 6:6 -c

for $7$-node trees.

Here's the 6 to 8 vertex trees below (it could easily extend this table to 15-node graphs, and beyond that with a bit of effort):

6-vertex

7-vertex

8-vertex

$\endgroup$
  • $\begingroup$ Thanks! It's good to know that the trees are easy to programmatically generate with this tool. The diagrams it produces are pretty compact, though. (Compare with the diagrams in Harary, which are much easier to read.) Can the geng be instructed to draw the diagrams without overlapping edges? $\endgroup$ – Psychonaut May 31 '13 at 14:32
  • 1
    $\begingroup$ Geng can't draw the graphs; I drew them myself via tikz and LaTeX just putting the nodes in a circle. There will be other (more ways to draw graphs, one visually pleasing way is the force directed method (Yifan Hu; pdf). $\endgroup$ – Douglas S. Stones May 31 '13 at 15:09
1
$\begingroup$

Frank Harary's Graph Theory has all the trees from p = 1 to p=10 displayed on pp. 233-234; the 10-vertex trees take up the whole page 234.

$\endgroup$
  • $\begingroup$ Thanks! I would have liked to accept both this answer and the one from @Douglas – the graphs in Harary are beautifully presented, though with geng I can generate trees of any order and (with a little work) can render them however I want. $\endgroup$ – Psychonaut Jun 3 '13 at 7:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.