Matchstick graphs

  

Want to know what a matchstick graph is? Take a look at the definition on Wikipedia.

   

The catalog

   

Here is a catalog of matchstick graphs with up to 10 edges (the 2 others are here if you want to have a look before downloading the big one):

   

(26 pages, 791 KB)

(54 pages, 1 821 KB)

(136 pages, 4 865 KB)

   

I thank Raffaele Salvia for his catalog of matchstick graphs with up to 9 edges which helped me a lot to create and debug the program used to generate the catalog.

   

How to read the catalog?

   

Matchstick graphs are classified by categories.

A category contains all graphs with the same number of edges, the same number of regions (including the outer region) and the same maximum degree, which is the maximum number of edges per node.

Categories are sorted by increasing number of edges, then increasing number of regions, then increasing maximum degree.

Inside a category, graphs are classified by topological homeomorphism classes.

Each homeomorphism class has two indices:
   - Its index inside the list of homeomorphism classes of graphs which have the same number of edges.
   - Its index inside the category it belongs to (see example below).

The same way each matchstick graph has two indices:
   - Its index inside the list of graphs which have the same number of edges.
   - Its index inside the homeomorphism class it belongs to.

The last category of the catalog is the following:

Category 10.33: 10 edges, 5 regions, max degree = 6 (10-5-6): 3 homeomorphism classes, 3 graphs

The list of graphs with 10 edges is split in 33 categories.
The last one contains all graphs with 10 edges, 5 regions and whose maximum degree is 6.
This category can be represented by the triplet (10-5-6).
It contains 3 homeomorphism classes and 3 graphs.

The last homeomorphism class is the following:

Homeomorphism class 10.479 (10-5-6:3): 1 graph

There are 479 homeomorphism classes for graphs with 10 edges.
It’s the third class of the category (10-5-6) and it has a single graph.

The last graph is represented by the following numbers:

10.479.2008 (10-5-6:3:1)

There are 2,008 matchstick graphs with 10 edges.
It’s the first (and only) graph of the homeomorphism class 10-5-6:3.

   

Interested in verifying my work?

   

If you are interested in verifying my work, here is my data:

1. The program:

      Algorithm used by the program:

      Description of the program:

      Results of the program:

2. List of 2,008 matchstick graphs with 10 edges:

3. Eight non-matchstick graphs:

   

1. The first data is a program I wrote which generates all potential matchstick graphs.
The output is ten .txt files containing the list of potential matchstick graphs. A graph is described by the list of its edges, an edge being a couple of zero-based nodes indices.
On my computer it takes around one minute to generate the list of potential matchstick graphs with 9 edges and around 30 minutes to generate the list of potential matchstick graphs with 10 edges.
If you don't want to wait that long, you can download the result files (see the link above).
The program gives a maximum value for the number of matchstick graphs: the maximum number of matchstick graphs with 10 edges is 2,016.

2. The second data is a list of matchstick graphs.
For each matchstick graph, it contains:
    - The 2D coordinates of each node.
    - The indices of the two nodes of each edge.

With this data, you can easily verify that each graph in this list is a matchstick graph:
    - The graph is connected.
    - Two edges don't connect the same pair of nodes..
    - Two nodes don’t have the same 2D coordinates.
    - The distance between two connected nodes is 1.
    - Edges don’t cross each other when they are represented as line segments.

This list contains 2,008 matchstick graphs with 10 edges.
Therefore the number of matchstick graphs with 10 edges is somewhere between 2,008 and 2,016.

3. The third data is a description (the indices of the 2 nodes of each edge) of the 8 graphs found by the program which are not in the list of matchstick graphs.
You can verify that they are not matchstick graphs.

   

If you have found a graph in the catalog and you want to get the 2D coordinates of its nodes, you can use the following file: it gives for each 10-edge graph its index inside the file '10-edge graphs.txt' stored in the '2,008 matchstick graphs with 10 edges.zip' archive.

   

Future work

   

I'm currently working on matchstick graphs with 11, 12 and 13 edges.