About my Math & CS scientific research

articles
Prof. RNDr. Petr Hliněný, Ph.D.

@ynenilhfi.muni.cz
FI research group
Faculty of Informatics MU Brno, CZ

If you love discrete mathematics, computer science, and mainly graphs more than anything else, then ...  Welcome!

Scientific research network

Local research team at Faculty of Informatics MU Brno, CZ:

Collaboration with members of institutions:

  • Charles University, Prague CZ; University of Warwick, UK; University Osnabrueck, Germany; RWTH Aachen University, Germany; University of Bergen, Norway; Universidad Autonoma de San Luis Potosi, Mexico; ...
Current research grants
  • PI - Czech Science Foundation (GAČR):
    • 6 research grants successfully finished prior to 2020, lastly 17-00837S "Structural properties, parameterized tractability and hardness in combinatorial problems",
    • now investigating 20-04567S "Structure of tractable instances of hard algorithmic problems on graphs".
  • Member - Institute of Theoretical Computer Science (ITI):
    • Czech national project 1M0545, 2005-2011,
    • then GAČR P202/12/G061, 2012-2018.

Research opportunities for students

Even if you are a young student at MU, you do not have to stay aside and may do something more than other students - say also with our research group...

Our research group welcomes all students interested in a theoretical research, both from Informatics and Mathematics. See below for a research statement. And, especially for keen first year students, come to our FI:IV119 Seminar on Discrete Mathematical Methods in Spring.

  • See, e.g., the current Bc/Ms thesis topics for an inspiration,
  • or inquire about PhD study under my supervision at FI MU Brno, CZ  (with stipend, good foreign applicants welcome).
    • Generally speaking, any theoretical research into graphs (with emphasis on structural and topological graph theory) and into graph algorithms and logic on graphs (with emphasis on parameterized complexity) can be discussed for a PhD.
    • Refer to the general admission procedure and special PhD calls.
  • Young students may have a first taste of real scientific research at the SVOČ student scientific competition.

IV125 Seminar

Having multiple seminar groups every semester (with different teachers), choose your favourite topic from the list (hint: choose graphs/combinatorics/geometry...).

Students' FI:IV119 Seminar on Discrete Mathematical Methods

This is an informal Spring seminar for all students who like mathematics, and especially beatiful mathematical problems, solutions, and proofs - as presented to us by famous "Proofs from THE BOOK". If you have ever tried "Mathematical olympiad" or other math competitions at elementary and high schools, then drop by and see how easy is to get from math fun to serious real science. Especially first year students with interest in math are most warmly welcome!

  • For all young students who like nice clean mathematics, no prerequisites required.
    Official seminar entry in IS
  • Spring 2020 seminar: in C417, but now only online (COVID-19!).
    • So, which problems to deal with this year? We will (traditionally) begin with the number of primes, and we will also look this year at various proofs of Euler's formula... (see this) Then we will pick other nice problems (and their solutions) from number theory, discrete geometry, combinatorics and graphs...
    • Come and see us (even if you participated in a past year - we will study different topics of The Book)...
  • See also a list of past 2019 topics here.

Recent results and ongoing research (2018-20)

  • Finally, finishing a full asymptotic characterization of c-crossing-critical graphs for fixed c>2. Joint work with Z. Dvořák and B. Mohar (SoCG2018). Then characterising the elusive case of c-crossing-critical graphs with unbounded max degree, which happens exactly for c>12. Joint work with many... (SoCG2019).
  • Initiating research of structural width parameters in discrete geometry - formulating and studying the clique-width of point configurations (submitted).
  • Conflict-free colour guarding of polygons - the vertex-to-point guarding scenario; additive constant approximation in special cases, and upper bounds in general (COCOA2019 and submitted update).
  • Complexity of (ordinary) colouring on polygon visibility graphs - hard from 5 colours on simple polygons and from 4 colours on non-simple (FSTTCS2017 and submitted improvement, with Cagirici and Roy).
  • A short new proof of Euler-Poincare Formula in every dimension, not using shellability of polytopes.

  • See also the publication list for the recent (submitted) entries.
Research topics: Structural width parameters in algorithms

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 (giving so called FPT or XP algorithms), as for instance various MSO-definable properties. The question of how to obtain such low degree structural decompositions is also studied, e.g. obtaining matroid branch-decomposition and graph rank-decomposition in FPT.

Our research directions include special emphasis on directed graph width measures, on getting complexity lower bounds on tractability wrt. width parameters, and most recently, on measuring "depth" of a graph and on kernelization results using new structural parameters.

Key and/or recent publications:
Research topics: MSO / FO logic and algorithms

Following on the previous topic, we particularly focus on algorithmic metatheorems which express a whole class of problems by means of a logical language, and then provide general (parameterized) algorithms for solving them. Prime role is played here by the new depth measures (shrub-depth) and their properties, and by a general question of how high is "logical/descriptive complexity" of a graph or graph class. The question of what are the limits (lower bounds) of this approach, is also considered. Other important results have been obtained for FO properties on posets of bounded width. Most recent direction focuses on FO properties of geometrically-defined graphs.

Key and/or recent publications:
  • 2019 (co-authors F. Pokrývka, B. Roy):   FO model checking of geometric graphs.  Computational Geometry: Theory and Applications 78 (2019), 1--19.   URL: arxiv.org/abs/1709.03701. DOI 10.1016/j.comgeo.2018.10.001. © Elsevier B.V.
  • 2019 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez):   Shrub-depth: Capturing Height of Dense Graphs.  Logical Methods in Computer Science 15 (2019), 7:1--7:25.   URL: arxiv.org/abs/1707.00359. DOI 10.23638/LMCS-15(1:7)2019.
  • 2017 (co-authors J. Gajarský, T. Kaiser, D. Král', M. Kupec, J. Obdržálek, S. Ordyniak, V. Tuma):   First order limits of sparse graphs: Plane trees and path-width.  Random Structures & Algorithms 50 (2017), 612--635.   URL: arxiv.org/abs/1504.08122. DOI 10.1002/rsa.20676. © John Wiley & Sons, Inc.
  • 2016 (co-authors J. Gajarský, D. Lokshtanov, J. Obdržálek, M.S. Ramanujan):   A New Perspective on FO Model Checking of Dense Graph Classes.  In: LICS 2016, ACM (2016), 176--184.   DOI 10.1145/2933575.2935314. Preprint/file.
  • 2015 (co-authors J. Gajarský, D. Lokshtanov, J. Obdržálek, S. Ordyniak, M.S. Ramanujan, S. Saurabh):   FO Model Checking on Posets of Bounded Width.  In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, IEEE (2015), 963--974.   URL: arxiv.org/abs/1504.04115. DOI 10.1109/FOCS.2015.63.
  • 2015 (co-author J. Gajarský):   Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences.  Logical Methods in Computer Science 11(1) (2015), paper 19.   URL: arxiv.org/abs/1204.5194. DOI 10.2168/LMCS-11(1:19)2015.
  • 2012 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez, R. Ramadurai):   When Trees Grow Low: Shrubs and Fast MSO1.  In: Math Foundations of Computer Science MFCS 2012, Lecture Notes in Computer Science 7464, Springer (2012), 419--430.   DOI 10.1007/978-3-642-32589-2_38. © Springer-Verlag. Preprint/file.
Research topics: Graph crossing number, structural and algorithmic

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 first interest is in finding good efficient approximation algorithms 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 related to this problem. We are now particularly looking at an approximate structural description of crossing-critical graphs, and on strengthening known algorithmic and hardness results on very special classes of graphs.

Key and/or recent publications:
Research topics: Discrete geometry and geometric graphs

This research direction studies some discrete geometrical questions related to graphs, recently focusing on visibility graphs and polygon guarding. A very new direction is that extending the notion of (graph) clique-width to the order type of point configurations.

Key and/or recent publications:
  • 2020 (co-authors O. Cagirici, F. Pokrývka, A. Sankaran):   Clique-Width of Point Configurations.  In: Graph-Theoretic Concepts in Computer Science, WG 2020, Lecture Notes in Computer Science ???, Springer (2020), to appear.   URL: arxiv.org/abs/2004.02282.
  • 2020 (co-authors O. Cagirici, S.K. Ghosh, B. Roy):   On conflict-free chromatic guarding of simple polygons.  Submitted (2020), 26 p.   URL: arxiv.org/abs/1904.08624.
  • 2019 (co-authors F. Pokrývka, B. Roy):   FO model checking of geometric graphs.  Computational Geometry: Theory and Applications 78 (2019), 1--19.   URL: arxiv.org/abs/1709.03701. DOI 10.1016/j.comgeo.2018.10.001. © Elsevier B.V.
  • 2018 (co-authors O. Cagirici, B. Roy):   On Colourability of Polygon Visibility Graphs.  In: FSTTCS 2017, LIPIcs Vol. 93, Dagstuhl (2018), 21:1--21:14.   DOI 10.4230/LIPIcs.FSTTCS.2017.21.
  • 2017:   A Short Proof of Euler--Poincaré Formula.  manuscript (2017), 5 p.   URL: arxiv.org/abs/1612.01271.
Research topics: Planar covers and emulators

This last research direction deals with just a small mathematical puzzle - the questions about which nonplanar graphs have finite planar covers (Negami's conjecture) and emulators (initiated by old Fellows' work). Briefly describing, a graph G has a planar cover (emulator) of there is a planar graph H and a locally bijective (surjective) homomorphism from H to G. On the one hand, Negami's conjecture states that finite planar covers exist exactly for projective-planar graphs. On the other hand, analogical conjecture about planar emulators was disproved in 2008 by Rieck-Yamashita, and now we have got many more strange counterexamples to that. Both these problems are still wide open.

Key publications:
Research topics: Route planning in huge graphs (road networks)

We are also investigating some new directions in the route planning problem (as e.g. in GPS navigations), both on theoretical and experimental sides. The particular emphasis of our approach is on two points - to get "reasonable" routes, and to make the preprocessed data for fast queries as small as possible (currently below 1% of the map size). We approach both objectives with a newly suggested notion of "scope".

Key publications: