Structural graph theory and parameterized algorithmics

Many practical algorithmic tasks have a core based on discrete structures such as graphs, digraphs, or matroids. Hence efficient solutions of these tasks require deep knowledge of the underlying theory of discrete mathematics. For instance, the following interesting practical problems have nice solutions provided by discrete mathematics:

• Finding the shortest path in a graph using Dijkstra's algorithm or its A* modification, or applying recent new concepts such as reach or contraction hierarchies.
• Network flows giving nice solutions to practical transport or connectivity problems, and having other often unexpected applications.
• Various problems in combinatorial optimization such as the minimum spanning tree or maximum matching problems solved by very elegant theoretical algorithms.

Our young and growing group focuses on using some of the very new ("structural") trends in discrete mathematics / graph theory and its algorithmic applications. Our aim is to contribute both on the theory side and in computing applications of the new findings.

Current team members

Main research objectives

• Width parameters of graphs and digraphs
  In this area we study traditional as well as some new parameters describing the "width" of combinatorial objects (in the sense of complexity, how much they "resemble" trivial input structures like trees) -- tree-width, branch-width, rank-width, DAG-width, or DAG-depth, to mention just a few. The expected outcome is that on input objects of low width, many otherwise hard algorithmic problems become tractable, as for instance various MSO-definable properties. The question of how to obtain such low width/degree decompositions is also studied.
• Logic (MSO/FO) in parameterized algorithms
  This follows on the previous topic, focusing on ways of expressing algorithmic problems in logical language (of variuous power) in order to provide meta-algorithms efficiently solving all problems with such expressions on specific classes of graphs.
• Graph crossing number
  This research direction copes with the problem to draw a graph with the least possible number of edge crossings, which appears to be an unusually difficult algorithmic task. Our primary interest is in finding good efficient approximations of the crossing number (some of which are even practically implementable, a quite rare case in this area). Besides that we deal with theoretical research of crossing-critical graphs, and with computational hardness questions of this problem.
• Geometric and topological graphs
  This topic includes some additional "small" research objectives, among which we mention the following two: First, a long term study of the planar cover and planar emulator problems (cf. Negami's planar cover conjecture). Second, an interest in applying some structural graph ideas to provide yet new concepts and algorithms for the practical route planning problem (e.g., for GPS navigation).

Information for students

Our research group offers for students

• an opportunity to join theoretical research on the highest international level (with publications in some of the top scientific journal in discrete mathematics or theoretical CS), and to have a perspective of continuing study on the Ph.D. level and starting an academic career,

and at the same time possibilities

• to work on specific project applying graphs and discrete mathematics in computer science.

More detailed information can be obtained from our team members, in the Seminar on Discrete Mathematical Methods IV119, or in some of the following graduate courses (all in English): MA010, MA051, MA052, MA053, IA102.

Interested senior students are also encouraged to participate in the Working Seminar on Formal Models, Discrete Structures, and Algorithms.

Participation in research projects

• Graph Drawings and Representations GraDR

  part of the EuroGIGA Programme (EUROCORES), 2011-2013.

• Well-structured combinatorial classes, width parameters, and design of efficient algorithms

  Grant GAČR P202/11/0196, 2011-2013, in collaboration with ZČU Plzeň (Dan Kráľ).

• Institute for Theoretical Computer Science (ITI)

  Czech national project 1M0545, 2005-2011. Now GAČR P202/12/G061, 2012-2018.

Cooperation with foreign researcher centers

• Theoretical Computer Science, RWTH Aachen, Germany, Prof. Peter Rossmanith et al: billateral research grant in 2009-2010
• Algorithm Engineering, University Jena, Germany, Dr. Markus Chimani: joint participation in the GraDR project 2011-2013
• Instituto de Física, Universidad Autonoma de San Luis Potosi, Mexico. Prof. Gelasio Salazar
• Dept. of Mathematical Sciences, KAIST, Korea. Dr. Sang-il Oum

Contact

• Homepage
• About the faculty
• Admission
• Studies
• Projects
• Research and development
  • Laboratories
  • Research centers
  • Informatics colloquium
  • Technical Reports
  • Forms
  • Contacts
• International studies
• E-learning
• Industrial partners
• News
• Contacts