Projects / Programmes
Structural, optimization, and algorithmic problems in geometric and topological graph representations
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
topological graph theory, algorithms, optimization in graphs, crossing numbers, planar graphs, intersection graphs
Researchers (23)
Organisations (3)
Abstract
Ubiquitousness of graphs as models and growing popularity of graph theory research has resulted in transcending graphs as strictly discrete structures. Models relying on very large graphs have been developed in several sciences. While traditional graph theory deals with small graphs and their properties, these interests drive its development towards large, infinite graphs, random graphs, and more complex objects, such as infinite graph families or graph limits. Both topological and geometric graph theory address problems related to such objects and investigate their structure and applications in theory and practice of optimization, algorithms and data structures. In the project, we will address structural, optimization, and algorithmic problems in geometric and topological graph representations. The first work package will investigate structure of representations of finite graphs as geometric or topological objects. Specifically, we will continue our research on the structure of crossing critical graphs, representativity of embeddings and surface triangulations. The second work package will continue development of limit theory of optimal or locally optimal graph drawings in connection to various models of random drawings of graphs. The structural theory developed will have the aim to provide new insights into asymptotic (possibly even exact) version of the Harrary-Hill-Guy conjecture from 1963 and/or Turan - Zarankiewicz conjecture from 1954. Through relation to geometric drawings of graphs, we hope to improve the current understanding of the Sylvester four-point problem from 1865. The third work package will address algorithmic and modelling applications of the structural results of the first two packages. As a sample of planned results, distance-related problems in planar graphs are related to routing problems, geometric intersection graphs are related to motion planning and image processing, limit objects of graphs are related to models of Hebbian learning, psychological models of optimal experience, and learning of artificial neural networks. The tools used in development of results on these topics include Erdős’ probabilistic method, excluded minor structure results by Robertson and Seymour, Szemerédi’s regularity lemma, and more recent graph limits pioneered by Lovász, together with structural results on graph embeddings and graph drawings developed or formerly applied by the team and its co-authors (including bridges of graphs, theory of tiles, zip product, specific data structures for geometric graphs). Our project will combine the expertise of the project team at this frontier of graph theory research.
