A search for general and planar graphs without L-models.

Program searching for L-models of graphs. L-model is an intersection graph representation using "L"'s, that is 1-bend polylines using 2 fixed directions (horizontal/vertical) where the bend is always the left-bottom-most point.

We may assume the minimal counterexample to be 1-connected (disconnected graphs can be drawn by components) and to have minimal degree at least 2 (leaves can be always drawn).

Two hypothesised no-L-model planar graph candidates and their L-models found using the program are included in graphs/.

Some large data-files can be found at the KAM computer kamenolom in /aux/gavento/lshape-data/.

By Tomáš Gavenčiak ([email protected]), 2012. Please let me know if you find out anything interesting using this tool.

Clone this repo using git clone https://github.com/gavento/l-model.git.

You need the Protocol buffer compiler and libraries (packages protobuf-compiler and libprotobuf-dev in Debian). You also need a working C++ compiler.

For graph6 format support, you need nauty-24r2. Run make get-nauty to download and compile it. This needs wget. Then run make all.

To only build the plantri version, run make lmodel-plantri.

./lmodel-nauty reads graphs in "graph6" format, ./lmodel-plantri reads graphs in "plantri" format, both programs read one graph per line from STDIN. The programs search for an L-model of the graph and have the same output.

• STDOUT contains only progress information (every 10000 graphs and in the end) prefixed by "I" and the graphs that do NOT have a representation prefixed by "N".
• STDERR contains various verbose information about the graph being processed and one representation, if any.

The STDERR output can be customised in the makefile (do not forget to run make clean all when making changes).

• WRITE_GRAPH [default on] - write the graph in a human-readable format
• WRITE_PROTOBUF [default off] - write the internal protocol buffer of the representation
• WRITE_DEPTHS [default off] - write the branching statistics (hits per recursion level)
• WRITE_SOLUTION [default off] - write soultion protocol buffer (if found)
• WRITE_GNUPLOT [default on] - write GnuPlot commands to plot the representation found (if found)

Each of the sections represents a class of graphs being examined. All general graphs were generated by nauty (using geng) and general planar graphs by plantri (using plantri -p). The used limitations on the graphs considered include vertex count, minimal degree and vertex connectivity.

The results also include the machine used, number of processes and some time statistics.

plantri45/plantri -m2 -c1 -p 10 -a
tot user 43m, all have L-models

plantri45/plantri -m2 -c1 -p 11 -a
tot user 40h, all have L-models

Assumptions on mindeg and connectivity of a min. counterexample are unproven, but sound reasonable and limit the number of candidates.

plantri45/plantri -m3 -c3 -p 11 -a
@kamisama 4x, tot user 54m, 0.0073 s/graph, all have L-models

plantri45/plantri -m3 -c3 -p 12 -a
@kamenolom 16x, approx. 0.067s/g, cca 119h total, all have L-models

./nauty24r2/geng -c -d2 8 -g
all have L-models

./nauty24r2/geng -c -d2 9 -g
@kamenolom 1x, 260s, all but one have L-models

The graph HEhbtjK has no L-shape representation. The graph neighbourhoods:

0 : 3 4 7 8;
1 : 3 5 6 8;
2 : 4 5 6 7;
3 : 0 1 6 7;
4 : 0 2 6 8;
5 : 1 2 7 8;
6 : 1 2 3 4;
7 : 0 2 3 5;
8 : 0 1 4 5;

There are too many graphs without models to be considered interesting, see experiment below.

./nauty24r2/geng -c -d2 10 -u
est. 22h runtime, NOT RUN

Assumption on 2-connectivity of a min. counterexample is unproven, but sound reasonable and limits the number of candidates and the 2-connected 10-vertex graphs without models seem more interesting.

./geng 8 -C -d2
@kamenolom, 4.798s, 0.00065 s/graph, all have L-models

./geng 9 -C -d2
@kamenolom, 9m34.006s, 0.003 s/graph, all but "HEhbtjK" have L-models (see above)

./geng 10 -C -d2
@kamenolom 16x, total 22h, 0.008 s/graph, 23 graphs without L-model:

I?qrbYyt_
IEhbtjK}?
IEhbtjK{_
IEhbtjKu_
IEhbtjK]_
IEhbtjKx_
IEhbtjK~?
IEhbtjK}_
IEhbtjK|_
IEhbtjKmo
IEhbtjK~_
IEhbtjK}o
IEhbtjK~o
IEhbtjK~w
I?qdUh{[o
I?qbByyt_
ICpelXwkg
I?qduhk[o
I?qduh{[o
ICpddXit_
ICR`upuj_
I?rDrpulO
IUZurzmmo