Topological containment and the Hajos Conjecture: new structure theorems from computer search

Topological containment is one of the oldest and most fundamental order relations in graph theory, and is important in embeddability problems such as planarity. However, it is very difficult to characterise graphs that do not topologically contain some given graph. We propose to use new techniques using computer search to develop new characterisations, and hence efficient algorithms, for some major open problems in topological containment. For example, we propose to characterise graphs that do not topologically contain the complete graph on five vertices, which should allow us to attack the first unsolved case of a famous conjecture due to Hajos which has remained open since the 1940s.