Graph Minor Theory in three dimensions and Connectivity

Graph Minor Theory sits at the interface between Topology and Graph Theory, with many algorithmic applications. The area started with Kuratowski's characterisation of planarity in terms of forbidden minors as well as the famous Hadwiger Conjecture, which would be a far reaching generalisation of the famous Four-Colour-Theorem. An important aspect of Graph Minor Theory is the connection between embeddings of graphs in 2-dimensional surfaces and the Minor Relation. Here a minor of a graph is obtained by deleting edges and contracting connected edge sets to single vertices. In the context of plane graphs the minor relation is particularly natural; it is equivalent to the subgraph relation combined with planar duality. The discovery of this connection began with Kuratowski's theorem in the 1930s and led to the proof of the Robertson-Seymour Theorem, which is often regarded as the deepest theorem of Combinatorics today.

The Graph Minor Theory of Robertson and Seymour has had a transformative impact on Combinatorics as a whole with deep implications to Computer Science. In very rough terms, their structure theorem establishes a connection between the minor relation on graphs and embeddings of graphs in 2-dimensional surfaces. The simplest example of this connection is Kuratowski's planarity criterion from 1930, which characterises the class of planar graphs in terms of forbidden minors. Recently, I have been able to prove a 3-dimensional analogue of Kuratowski's theorem, answering questions of Lovasz, Pardon and Wagner. This suggests that the ideas and methods of Graph Minors can be extended from 2 to 3 dimensions. Do they offer new approaches to well-known problems on 3-manifolds?

Such problems occur both in Pure Mathematics and Engineering Applications: indeed, Perelman proved that any simply connected compact 3-manifold is isomorphic to the 3-sphere, solving one of the 7 millennium problems. One of the ingredients of the proof of my new 3D-Kuratowski theorem is Perelman's theorem, and thus my result provides a link between Combinatorics, Geometry and Topology.

Engineering applications arise from the fact that many structures in the real world can be modelled by so called 2-complexes; that is, objects that can be obtained by gluing together triangular faces at their boundaries. Examples include human-built structures like skyscrapers or cars, physical ones like foams and intestines give medical applications. It is a fundamental question when such 2-complexes can be embedded in the real 3-dimensional world. More specifically, given a 2-complex in an abstract way, can you assemble its faces - using bending, stretching and twisting - in 3-space so that the faces do not pierce each other? This project will yield a better combinatorial understanding of such problems, which in turn will lead to better algorithms for the corresponding computational problems.

My main aim in this programme is to develop a Graph Minor Theory for 2-complexes. I believe that this has the potential to become a rich new theory, with many exciting questions, and connections to Combinatorics (in particular Graph Minors and connectivity), Algebra (more specifically Matroid Theory), Differential Geometry and Topology of 3-manifolds and Algorithms. Recent successes in this area include my quadratic time algorithm to check embeddability of simply connected 2-complexes in 3-space - and during this programme I intend to extend this further.

A second strand of this programme is the development of new methods for extremal questions in graph minors and connectivity. On the one hand connectivity questions arise in applications (such as reliability questions for the internet or electrical power networks), on the other hand they provide fundamental tools for the theory (such as Tutte's Decomposition Theorem or the Tangle-Tree Theorem of Robertson and Seymour). This programme contains a new approach towards a fundamental problem in this area from the 70s.

I am dedicated to my project and will ensure that it has as much impact as possible, both academically and within the wider community. Already at this stage, the following potential for impact is visible.

1) Impact through Algorithms.
I very much expect that some of the results of this project will have algorithmic consequences. Such algorithms are likely to be finally applied in the areas of Solid Modelling, Geographic Information Systems and Computational Topology for Structural Molecular Biology. Recent successes in this area include my quadratic time algorithm to check embeddability of simply connected 2-complexes in 3-space - and during this programme I intend to extend this further.

2) Strengthening the UK research landscape.
This project fits well with current strategic challenges set out in the `EPSRC Pure Mathematics Evidence and Engament workshop report' in September 2016, see the Pathways to Impact Statement for details. Similar points were also raised in the earlier EPSRC report entitled `International Review of Mathematical Sciences' from 2010. The research proposed here is indeed at the connection of Structural Graph Theory and Computer Science/Algorithms. However, it additionally involves ideas from 3-dimensional Topology and Differential Geometry, which have not been combined in this way before, in the US or elsewhere.

3) Workshop.
One of my aims is to build bridges between the somewhat disjoint communities in Graph Minors and Computational Geometry. For example, I am planning to have an intradisciplinary workshop at the beginning of the project bringing together researchers from these areas.

4) Junior Scholars.
The PhD students and PDRAs that I will supervise in this project will develop new skills and gain experience by working on cutting edge research problems. I enjoy being part of shaping the future generation of researchers. I am very excited about starting to supervise my first PhD student, Tsvetomir Mihaylov (currently in Oxford), in autumn this year. Currently I am supervising Lyuben Lichev, a very bright and ambitious Master's student from Lyon (France).

5) Future applications to Computer-aided design, short CAD.
CAD describes a class of computer programmes that help humans to design 3-dimensional objects. They are extensively used in many applications, including automotive, shipbuilding, and aerospace industries, industrial as well as architectural design. Currently in such programmes the user specifies the shapes they want to connect and the length of these objects and CAD visualises it, allowing the user further improvements.

But why is it not far more automated? More precisely, the user specifies how the shapes are to be connected. And they also give some length - but by far not all of them. Then the computer determines the remaining length and how these shapes are bended and knotted (or otherwise gives a proof that these shapes cannot be connected in the specified way), and this way it produces a prototype.

I believe that the main reason why it is not done this way is that this would be computationally unfeasible at the moment - because the underlying mathematics has not been developed yet. Indeed, one of the many consequences of "Sphere Recognition" - which I have identified as a long term goal in this programme - would be the existence of such a computer programme. Objectives 1-5,7,8 would provide partial progress in this direction.