About my Math & CS scientific research

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

@ynenilhfi.muni.cz
FI research group DIMEA
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:

  • Petr Hliněný (team head),
    • Grzegorz Guśpiel (postdoc researcher 2023-2024).
    • Deniz Agaoglu, Filip Pokrývka, Shubhang Mittal (Ph.D. students).
      New doctoral applicants are welcome, refer particularly to the current PhD calls with additional funding.
    • Jakub Balabán, Jan Jedelský (Master students), Adam Straka, Tai Phat Pham (Bachelor students).
  • See also the DIMEA Laboratory - with Prof. Daniel Král, and the DIMEA + Formela seminar.
Research projects and grants
  • PI - Czech Science Foundation (GAČR):
    • 7 research grants successfully finished prior to 2023, lastly 20-04567S "Structure of tractable instances of hard algorithmic problems on graphs".

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...

Our research group welcomes all students interested in a theoretical research, both from Informatics and Mathematics. See below for a research statement.

  • See the research-oriented student seminars, and the aforementioned DIMEA + Formela seminar featuring mainly talks by external guests and discussions with them.
  • Consider, 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.

Recent results and ongoing research (2020-23)

  • Following the asymptotic characterization of c-crossing-critical graphs for fixed c>2, obtained exact characterization of when c-crossing-critical graphs can have unbounded degree (with D. Bokal, Z. Dvořák, J. Leanos, B. Mohar, T. Wiedera, Combinatorica 2022): Only bounded degrees for c<=12, and any combination of any degree for each c>=13 is possible. Subsequent slight improvements with M. Korbela.
  • Partially predrawn crossing number - the usual crossing number under a restriction that the given subgraph must be preserved as predrawn, having an FPT algorithm wrt. the solution value (with T. Hamm, SoCG 2021), ongoing research of structural properties of this variant.
  • Starting research of structural width parameters in discrete geometry - formulating and studying the clique-width of point sets - configurations (with O.Cagirici, F. Pokrývka and A. Sankaran, JCT-B 2023).
  • A short new proof of Euler-Poincare Formula in every dimension, not using shellability of polytopes (EuroComb 2021).
  • Efficient isomorphism for intersection graphs -- FPT for Sd-graphs and T-graphs, and ongoing research towards H-graphs with unicyclic H (with D. Agaoglu Cagirici, Algorithmica 2023 ++), while this problem is GI-hard for all H having at least two cycles.
  • Twin-width of planar graphs -- following previously obtained bounds in the order of hundreds, we have succeded to bring the upper bound down to 8 (with J. Jedelský), while the currently best lower bound is 7 (Král and Lamaison). Really close, and we hope to match 7 soon...

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

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, shrub-depth, or new twin-width, or, 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.

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 measures (shrub-depth, newly twin-width) 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, and for FO interpretations/transductions (e.g. for geometrically defined graphs).

Key and/or recent publications:
  • 2023 (co-authors O. Cagirici, F. Pokrývka, A. Sankaran):   Clique-Width of Point Configurations.  J. of Combinatorial Theory ser. B 158 (2023), 43--73.   URL: arxiv.org/abs/2004.02282. DOI 10.1016/j.jctb.2021.09.001.
  • 2022 (co-authors J. Balabán, J. Jedelský):   Twin-width and Transductions of Proper k-Mixed-Thin Graphs.  In: Graph-Theoretic Concepts in Computer Science, WG 2022, Lecture Notes in Computer Science 13453, Springer (2022), 43--55.   URL: arxiv.org/abs/2202.12536. DOI 10.1007/978-3-031-15914-5_4.
  • 2020 (co-authors J. Gajarský, D. Lokshtanov, J. Obdržálek, M.S. Ramanujan):   A New Perspective on FO Model Checking of Dense Graph Classes.  ACM Transactions on Computational Logic 21 (2020), #28.   URL: arxiv.org/abs/1805.01823. DOI 10.1145/3383206.
  • 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.
  • 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.
  • 2014 (co-authors R. Ganian, A. Langer, J. Obdržálek, P. Rossmanith, S. Sikdar):   Lower Bounds on the Complexity of MSO1 Model-Checking.  Journal of Computer and System Sciences 80 (2014), 180--194.   URL: arxiv.org/abs/1109.5804. DOI 10.1016/j.jcss.2013.07.005. © Elsevier B.V.
  • 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 - my favourite one, 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 discrete geometrical questions related to graphs. I was active in this area while being student and postdoc, and recently I have returned to it, focusing now on visibility graphs and polygon guarding, and interscetion H-graphs. A related new direction is that extending the notion of (graph) clique-width to the order type of point configurations.

Key and/or recent publications:
Research topics: Planar covers and emulators

This past research direction dealt with the following 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 we have got many more strange counterexamples to that. Definite answers to both these problems are still wide open.

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

In past we were investigating some new directions in the route planning problem (as e.g. in GPS navigations), both on theoretical and experimental side. The particular emphasis of our approach was on two points - to get "reasonable" routes, and to make the preprocessed data for fast queries as small as possible (got below 1% of the map size), for which we suggested a new notion of "scope".

Key publications: