Authors: Édouard Bonnet, Florian Sikora, Paweł Rzążewski
We share two python files to experiment with disk graphs, test conjecture, and draw figures:
-
disks.py
-
toTikz.py
In disks.py, you will find functions to generate disk graphs, and to test if a given graph has a disk or a unit disk representation. toTikz.py permits to generate latex code out of a disk representation generated by disks.py.
To recognize disk graphs, we rely on the optimizer/solver SCIP (http://scip.zib.de/) which performs very well as a solver of quadratic inequalities. If the graph has a disk representation and less than 25 vertices, it is likely that SCIP will find it within one minute. You will never obtain a certificate that a graph is not a disk graph from SCIP but the consequence of the previous sentence is that if, after 10 minutes, you still don't get a solution on a graph with around 25 vertices, with high probability your graph has no disk representation ;-)
The dependencies are listed below.
You need to install:
1- the python package python-networkx to handle graphs (apt-get install python-networkx)
2- the SCIP solver at http://scip.zib.de/#download
3- then, pyscipopt for the interface SCIP/python (pip install pyscipopt)
It is possible that everything goes smoothly. It is also possible that you get some errors from installing and running scip and pyscipopt. Maybe the following can help.
Step 1. should be straightforward. After step 2, you can try to run scip. If you get an error, you might want to try a different version of scip, perhaps 4.1.0. After step 3, you can try to import pyscipopt in python. If you get an error, try to downgrade to pyscipopt-1.2.0. It is also possible that your version of gfortran is too recent for pyscipopt. In that case, try to install gfortran-4.8 for instance.
Additionally, if you want to print the disk representation in pdf, you will need a standard texlive distribution.
You can address your question to edouard.bonnet@dauphine.fr