Graphs reveal abstract shapes

Gleb Nenashev will receive his doctoral degree in mathematics from Stockholm University in 2018. Thanks to a grant from the Knut and Alice Wallenberg Foundation, he will hold a postdoctoral position with Professor Alexander Postnikov at Massachusetts Institute of Technology, Cambridge, USA.

The main subject of the proposed research project focuses on triangulation. Simple triangulation methods were utilized by ancient Egyptians to measure the height of pyramids, and the ancient Greeks used it to calculate (with amazing accuracy) the circumference of the Earth. Subsequently, it became an important method for land surveyors and cartographers until the 1990s, when the satellite GPS measurements supplanted these ancient techniques.

The triangulations proposed in the current project are substantially more abstract. The objects to be triangulated are related to multi-dimensional convex polytopes. The problem becomes more complex in higher dimensions, especially as the number of vertices increases. For example, a flat rectangle has only two possible triangulations, whereas a polygon with five vertices can be triangulated in five ways. More complicated objects can consist of several polygons put together, like a square and hexagon with a common edge.

One basic idea for the project is to construct triangulations using methods from graph theory. A graph is a collection of points, or nodes, with lines connecting some nodes. A tree is a graph in which there is exactly one path between any two nodes. Such mathematical trees are commonly used by computer scientists and programmers to describe data storage and its algorithms. Applying the trees from graph theory to solve triangulation problems is the novel idea behind the proposed project.