1
$\begingroup$

I wanted to verify some graph properties on all possible graph enumerations (or graphs satisfying certain properties). There is a list of all the graphs upto 10 vertices here, but that is not sufficient for my use.

So I had two questions:

  1. Which would be the most user friendly and RAM efficient program/library to work with graphs, if I already have the graph with me.

  2. What would be an easy and efficient way to generate graphs satisfying certian conditions. I tried to search about Nauty over net but it is difficult to find a tutorial.

$\endgroup$
  • 1
    $\begingroup$ Try harder with nauty. $\endgroup$ – Yuval Filmus Jun 27 '18 at 20:10
  • $\begingroup$ This depends a lot on the conditions. Nauty and its utility programs are nice and flexible, but they obviously aren't suitable for everything. If you care about planar graphs, you can look at plantri (but again, its interface is very "nauty-like", or very much similar to your standard Unix program). $\endgroup$ – Juho Jun 27 '18 at 20:17
  • 1
    $\begingroup$ Essentially, you might just have to take Yuval's suggestion and try a little harder. After all, remember that this kind of software is usually intended for professional researchers and documentation can be scarce. $\endgroup$ – Juho Jun 27 '18 at 20:19
2
$\begingroup$

If you need to generate graphs, you can look at nauty: this is useful if you want to check whether a claim holds for all $n$-vertex graphs up to some small $n$. If you fancy planar graphs, you can have a look at plantri. I would not be surprised if you don't find tutorials, since this type of software is usually intended for professional researchers (but generally speaking, you should have little trouble in compiling and running if you are familiar with the typical Unix-like software).

To answer question 2, you can find online (via the nauty homepage, for instance) collections of small graphs with certain properties. House of Graphs is also pretty nice, but not exhaustive. If the properties you care about are exotic enough, you will have to come up with your own generator and/or just discard the graphs that don't satisfy your property from some collection of all small graphs.

To answer question 1, again, if you need efficiency, it will hard to beat something like nauty and its many utility programs. These are quite well-optimized and thoroughly used pieces of software. If you insist on more user friendliness at the expense of efficiency, I can recommend Mathematica. More generally, it is often the case you will have to write your own programs to strike the right balance between usability and efficiency.

There are also automated systems for suggesting conjectures, particularly in graph theory. One system I have successfully used is GraPHedron [1], but note that the system is currently unavailable. There are similar systems out there, and you should find pointers from [1] and the later papers that cite it.


[1] Mélot, Hadrien. "Facet defining inequalities among graph invariants: the system GraPHedron." Discrete Applied Mathematics 156.10 (2008): 1875-1891.

$\endgroup$

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.