Source-linked AI summary
House of Graphs: a database of interesting graphs
Gunnar Brinkmann, Kris Coolsaet, Jan Goedgebeur, Hadrien Melot
TL;DR
Graph collections grow too quickly for exhaustive testing, while a graph’s relevance depends on the problem being studied. House of Graphs addresses this by combining searchable and downloadable graph collections with a curated, user-extendable list of special graphs. It uses extremal graphs from GraPHedron and supports user submissions, although invariant-expression filters and PDF/JPG uploads remain future plans.
Problem
The rapid growth of graph collections makes exhaustive testing difficult, and graph relevance depends on the question being studied.
Method
House of Graphs combines searchable and downloadable graph collections with a curated list of special graphs and user submission capabilities.
Results
The database initially contained 1570 graphs, including GraPHedron extremal graphs and other graphs from mathematical studies and literature.
Takeaways & Limitations
The database provides a problem-oriented source of potentially relevant graphs and possible counterexamples that can grow as users contribute entries.
Takeaways & Limitations
Invariant-expression filters and PDF or JPG uploads for graph drawings were planned but not yet available.
Abstract
from arXiv · showhide
In this note we present House of Graphs (http://hog.grinvin.org) which is a new database of graphs. The key principle is to have a searchable database and offer -- next to complete lists of some graph classes -- also a list of special graphs that already turned out to be interesting and relevant in the study of graph theoretic problems or as counterexamples to conjectures. This list can be extended by users of the database.
1. Introduction
House of Graphs addresses the rapid growth of graph collections by combining searchable access with a curated set of graphs considered interesting or relevant to particular problems. Its initial contents include user-extendable special graphs, including extremal graphs identified through GraPHedron.
- 29.003.487.462.848.061 connected graphs with 14 vertices make exhaustive testing and even simple invariant computation difficult.
- Whether a graph is interesting or relevant depends strongly on the conjecture or question being studied.
- The database avoids an exact definition of interesting or relevant while allowing users to add graphs and identify relevant invariants.
- 1570 graphs were initially added, including extremal graphs, maximal triangle-free Ramsey graphs, and named graphs from the mathematical literature.
- GraPHedron identifies extremal graphs as vertices of polyhedra whose facets yield linear inequalities between selected graph invariants.
- Conglomerates group graphs at the same extremal point and are represented by a relatively small greedy-heuristic set because minimum set covering is NP-complete.
2. Functionality of the website
House of Graphs provides downloadable graph lists, searchable filtering, precomputed information for interesting graphs, and user submission of new entries. Search restrictions can be combined, while some planned capabilities and uploads are not yet available.
- 2. Functionality of the website: The website offers downloadable lists of interesting graphs, snarks, IPR-fullerenes, regular graphs, vertex-transitive graphs, and some planar graph classes.
- 2. Functionality of the website: Interesting graphs have precomputed invariants and embeddings, and browsing entries displays names, invariant values, relevant invariants, and comments.
- 2.1. Search functionality of the website: Search reduces the database to graphs satisfying criteria such as keywords, interestingness for an invariant, invariant ranges, or a specified graph.
- 2.1. Search functionality of the website: The planned invariant-expression filters and PDF or JPG graph-drawing uploads are not yet available.
- 2.1. Search functionality of the website: Several restriction steps can be combined; searching for girth 6, regularity, average degree 3, and 14 vertices returns the Heawood graph.
- 2.2. Submitting graphs to the site: Users can submit graphs through supported formats or editors; new entries accept names, construction details, conjecture-counterexample status, references, and interesting invariants.
- 2.2. Submitting graphs to the site: Invariant computations run in a background queue and may take milliseconds to days, with values potentially remaining unknown for very large graphs and NP-complete invariants.