Projects / Programmes
Crossing numbers and their applications
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
| Code |
Science |
Field |
| 1.01 |
Natural Sciences |
Mathematics |
topological graph theory, crossing numbers, graph drawing algorithms, structure of graph drawings, graph visualization
Researchers (17)
Organisations (3)
Abstract
Crossing number minimization is one of the fundamental problems in geometric graph theory. Despite long history and extreme applicability of crossing numbers, most of the basic questions about crossing numbers of graphs remain open and our current understanding is still quite limited. In the last 25 years, several breakthrough results have been made. However, research is stalled again because of lack of theoretical results. New natural variants of the crossing numbers, many of them motivated by applications, keep being proposed. The research community is more successful at proposing new fundamental problems about crossing numbers than closing them.
In the last few years, our research group has made several key contributions in this research area, especially in algorithmic questions and structural theory of crossing numbers. The objective of this project is to obtain a better understanding of crossing numbers of graphs through deeper study of structural properties of optimal drawings of graphs, algorithmic aspects, and the applied variants, including the minor crossing number, introduced in the recent years.
Significance for science
Our project presents basic research in a field connecting discrete mathematics – graph theory – and topology, whose applications reach through computer science – graph drawing algorithms – to all fields requiring efficient and clearly understandable visualization of graphs or networks. These include presentations of computer networks, telecommunication networks, electricity distribution networks, various pipelines and transportation networks in logistics and medicine (blood and neural networks), biological networks, social and collaboration networks etc.
We will investigate several problems that are open for some time, and the growing list of papers on these problems demonstrates their relevance. There are several tenths of papers published annually in the field of crossing numbers that demonstrate progress in understanding both the basic crossing number invariant as well as new applications of this and similar graph drawing concepts that are demonstrated in recent surveys. We expect that with the presented research on the crossing number problem, development of new algorithmic insights, and applications of these in specific problems from literature we will contribute significantly to better understanding of graph drawings and graph crossing numbers, which will be demonstrated through the citations of our results.
During the project we expect that we will be invited to deliver several invited plenary talks which will further emphasize the importance of our research achievements. In this way we will further increase the reputation of the Slovenian graph theory school.
Significance for the country
Both Slovenian and international companies have developed several solutions for graph – network visualization. Some of these solutions were developed by close collaborators of the project group. The project will help developing these solutions further: direct results of the project will be published papers and proof-of-concept algorithms on low technology readiness levels (TRL 1-3), which are regular outcome of basic research projects. The project members will promote these results to interested users through pedagogical engagement and consulting; BSc and MSc students will be able to develop algorithmic solutions to higher technology readiness levels (TRL 4-6) and the interested companies would be able to use those in their commercial solutions (TRL 7-9).
This collaboration can be well justified with our previous research that has led to a cooperation with the Slovenian industry from the technological development, mostly in the information and telecommunication technology. In the last period we have successfully cooperated in the projects Models and algorithms for employee scheduling (project ordered by HIT d.d., Nova Gorica), Algorithms for developing a model of working process (project ordered by ICIT, d.o.o., Šempeter pri Gorici), Optimal distribution among fuel stations (project ordered by Ultra d.o.o., Zagorje ob Savi), The application of the Q factor (SAIDI and SAIFI) in the methodology of determining distribution charges for power transmission and distribution grid (the project is done in collaboration with the institute Milan Vidmar), Graphs and telecommunication networks (IMFM and ISKRATEL, telekomunikacijski sistemi, d.o.o.), Graph minors, graphs on surfaces and networks (IMFM and Hermes Softlab Programska Oprema).
Most important scientific results
Interim report,
final report
Most important socioeconomically and culturally relevant results
Interim report,
final report
