Petr Hliněný

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

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

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

• Petr Hliněný (team head),
  • Shubhang Mittal, Jakub Balabán, Jan Jedelský (Ph.D. students).
    New doctoral applicants are welcome, refer to the admission page.
  • Adam Straka, Tai Phat Pham, Samuel Čepela, Lukáš Málik (Master students), Marek Štefaník (Bachelor students).
• See also the DIMEA Laboratory - with Prof. Daniel Král, and the Joint theory seminar.

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

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

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.

• 2024 (co-author J. Jedelský):   H-Clique-Width and a Hereditary Analogue of Product Structure.  In: MFCS, LIPiCS Vol. 306, Dagstuhl (2024), 61:1--61:16.   URL: arxiv.org/abs/2403.16789. DOI 10.4230/LIPIcs.MFCS.2024.61.
• 2023 (co-authors B. Bergougnoux, J. Gajarský, G. Guspiel, F. Pokrývka, M. Sokolowski):   Sparse Graphs of Twin-width 2 Have Bounded Tree-width.  In: ISAAC 2023, LIPiCS Vol. 283, Dagstuhl (2023), 11:1--11:13.   URL: arxiv.org/abs/2307.01732. DOI 10.4230/LIPIcs.ISAAC.2023.11.
• 2023:   Twin-width of Planar Graphs; a Short Proof.  In: Eurocomb'23, Proceedings, Masaryk University Press (2023), 595--600.   URL: arxiv.org/abs/2302.08938. DOI 10.5817/CZ.MUNI.EUROCOMB23-082.
• 2023 (co-author J. Jedelský):   Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar.  In: ICALP 2023, LIPiCS Vol. 261, Dagstuhl (2023), 75:1--75:18.   URL: arxiv.org/abs/2210.08620. DOI 10.4230/LIPIcs.ICALP.2023.75.
• 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.
• 2019 (co-authors J. Gajarský, M. Koutecký, S. Onn):   Parameterized Shifted Combinatorial Optimization.  Journal of Computer and System Sciences 99 (2019), 53--71.   URL: arxiv.org/abs/1702.06844. DOI 10.1016/j.jcss.2018.06.002. © Elsevier B.V.
• 2018:   Simpler Self-reduction Algorithm for Matroid Path-width.  SIAM J. Discrete Mathematics 32-2 (2018), 1425-1440.   URL: arxiv.org/abs/1605.09520. DOI 10.1137/17M1120129. © Society for Industrial and Applied Mathematics.
• 2017 (co-authors J. Gajarský, J. Obdržálek, S. Ordyniak, F. Reidl, P. Rossmanith, F. Sánchez Villaamil, S. Sikdar):   Kernelization Using Structural Parameters on Sparse Graph Classes.  Journal of Computer and System Sciences 84 (2017), 219--242.   URL: arxiv.org/abs/1302.6863. DOI 10.1016/j.jcss.2016.09.002. © Elsevier B.V.
• 2016 (co-authors R. Ganian, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar):   Are there any good digraph width measures?.  J. of Combinatorial Theory ser. B 116 (2016), 250--286.   URL: arxiv.org/abs/1004.1485. DOI 10.1016/j.jctb.2015.09.001. © Elsevier B.V.
• 2016 (co-authors O. Kwon, J. Obdržálek, S. Ordyniak):   Tree-depth and Vertex-minors.  European J. Combinatorics 56 (2016), 46--56.   URL: arxiv.org/abs/1403.7024. DOI 10.1016/j.ejc.2016.03.001. © Elsevier B.V.
• 2008 (co-author S. Oum):   Finding Branch-decompositions and Rank-decompositions.  SIAM J. Computing 38 (2008), 1012--1032.   DOI 10.1137/070685920. © Society for Industrial and Applied Mathematics. Preprint/file.

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

• 2024 (co-authors J. Balabán, J. Jedelský):   Twin-width and Transductions of Proper k-Mixed-Thin Graphs.  Discrete Mathematics 347 (2024), 113876.   URL: arxiv.org/abs/2202.12536. DOI 10.1016/j.disc.2024.113876.
• 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.
• 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.

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.

• 2023:   Complexity of Anchored Crossing Number and Crossing Number of Almost Planar Graphs.  Submitted (2023), 18 p.   URL: arxiv.org/abs/2306.03490.
• 2022 (co-authors D. Bokal, Z. Dvořák, J. Leanos, B. Mohar, T. Wiedera):   Bounded degree conjecture holds precisely for c-crossing-critical graphs with c <= 12.  Combinatorica 42 (2022), 701--728.   URL: arxiv.org/abs/1903.05363. DOI 10.1007/s00493-021-4285-3.
• 2022 (co-author T. Hamm):   Partially-Predrawn Crossing Number and the Critical Graphs.  Preprint (2022), 21 p.
• 2020 (co-authors M. Chimani, G. Salazar):   Toroidal Grid Minors and Stretch in Embedded Graphs.  J. of Combinatorial Theory ser. B 140 (2020), 323--371.   URL: arxiv.org/abs/1403.1273. DOI 10.1016/j.jctb.2019.05.009. © Elsevier B.V.
• 2019 (co-author A. Sankaran):   Exact Crossing Number Parameterized by Vertex Cover.  In: Graph Drawing 2019, Lecture Notes in Computer Science 11904, Springer (2019), 307--319.   URL: arxiv.org/abs/1906.06048. DOI 10.1007/978-3-030-35802-0_24.
• 2018 (co-authors Z. Dvořák, B. Mohar):   Structure and generation of crossing-critical graphs.  In: SoCG 2018, LIPIcs Vol. 99, Dagstuhl (2018), 33:1--33:14.   URL: arxiv.org/abs/1803.01931. DOI 10.4230/LIPIcs.SoCG.2018.33.
• 2018 (co-author C. Thomassen):   Deciding Parity of Graph Crossing Number.  SIAM J. Discrete Mathematics 32-3 (2018), 1962--1965.   DOI 10.1137/17M1137231. © Society for Industrial and Applied Mathematics. Preprint/file.
• 2017 (co-author M. Chimani):   A Tighter Insertion-based Approximation of the Crossing Number.  Journal of Combinatorial Optimization 33 (2017), 1183--1225.   URL: arxiv.org/abs/1104.5039. DOI 10.1007/s10878-016-0030-z. © Elsevier B.V.
• 2016 (co-author M. Derňár):   Crossing Number is Hard for Kernelization.  In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 42:1--42:10.   URL: arxiv.org/abs/1512.02379. DOI 10.4230/LIPIcs.SoCG.2016.42.
• 2016 (co-author M. Chimani):   Inserting Multiple Edges into a Planar Graph.  In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 30:1--30:15.   URL: arxiv.org/abs/1509.07952. DOI 10.4230/LIPIcs.SoCG.2016.30.
• 2010 (co-author M. Chimani):   Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface.  In: Symposium on Discrete Algorithms SODA 2010, ACM--SIAM (2010), 918--927.   URL: www.siam.org/proceedings/soda/2010/soda10.php. © Society for Industrial and Applied Mathematics. Preprint/file.
• 2010 (co-author G. Salazar):   Stars and Bonds in Crossing-Critical Graphs.  Journal of Graph Theory 65 (2010), 198--215.   DOI 10.1002/jgt.20473. © John Wiley & Sons, Inc. Preprint/file.
• 2006:   Crossing Number is Hard for Cubic Graphs.  J. of Combinatorial Theory ser. B 96 (2006), 455--471.   DOI 10.1016/j.jctb.2005.09.009. © Elsevier B.V. Preprint/file.

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.

• 2024 (co-authors O. Cagirici, B. Roy):   On Colourability of Polygon Visibility Graphs.  European J. Combinatorics 117 (2024), 103820.   URL: arxiv.org/abs/1906.01904. DOI 10.1016/j.ejc.2023.103820.
• 2023 (co-authors D. Agaoglu Cagirici, O. Cagirici, J. Derbisz, T.A. Hartmann, J. Kratochvíl, T. Krawczyk, P. Zeman):   Recognizing H-Graphs - Beyond Circular-Arc Graphs.  In: MFCS 2023, LIPiCS Vol. 272, Dagstuhl (2023), 8:1--8:14.   URL: arxiv.org/abs/2212.05433. DOI 10.4230/LIPIcs.MFCS.2023.8.
• 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.
• 2021:   A Short Proof of Euler--Poincaré Formula.  In: Extended Abstracts EuroComb 2021, Trends in Mathematics, Springer (2021), 92--96.   URL: arxiv.org/abs/1612.01271. DOI 10.1007/978-3-030-83823-2_15.
• 2019 (co-authors O. Cagirici, S.K. Ghosh, B. Roy):   On conflict-free chromatic guarding of simple polygons.  In: COCOA 2019, Lecture Notes in Computer Science 11949, Springer (2019), 601--612.   URL: arxiv.org/abs/1904.08624. DOI 10.1007/978-3-030-36412-0_49.
• 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.
• 2001:   An Addition to Art Galleries with Interior Walls.  Discrete Computational Geometry 25 (2001), 311--314.   DOI 10.1007/s004540010078.
• 1998:   Classes and recognition of curve contact graphs.  J. of Combinatorial Theory ser. B 74 (1998), 87--103.   DOI 10.1006/jctb.1998.1846. © Elsevier B.V. Preprint/file.

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.

• 2015 (co-author M. Derka):   Planar Emulators Conjecture Is Nearly True for Cubic Graphs.  European J. Combinatorics 48 (2015), 63--70.   DOI 10.1016/j.ejc.2015.02.009. © Elsevier B.V. Preprint/file.
• 2013 (co-authors M. Chimani, M. Derka, M. Klusáček):   How Not to Characterize Planar-emulable Graphs.  Advances in Applied Mathematics 50 (2013), 46--68.   URL: arxiv.org/abs/1107.0176. DOI 10.1016/j.aam.2012.06.004. © Elsevier B.V. Addendum.
• 2010:   20 Years of Negami's Planar Cover Conjecture.  Graphs and Combinatorics 26 (2010), 525--536.   DOI 10.1007/s00373-010-0934-9. © Springer-Verlag. Preprint/file. Addendum.
• 2004 (co-author R. Thomas):   On possible counterexamples to Negami's planar cover conjecture.  Journal of Graph Theory 46 (2004), 183--206.   DOI 10.1002/jgt.10177. © John Wiley & Sons, Inc. Preprint/file. Addendum.
• 1999:   Planar covers of graphs: Negami's conjecture.  PhD. Dissertation, School of Math., Georgia Institute of Technology (1999), 132 p.   Preprint/file.

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

• 2019 (co-authors R. Vodák, M. Bíl, T. Svoboda, Z. Křivánková, J. Kubeček, T. Rebok):   A deterministic approach for rapid identification of the critical links in networks.  PLOS ONE 14(7) (2019), e0219658.   DOI 10.1371/journal.pone.0219658.
• 2012 (co-author O. Moriš):   Generalized Maneuvers in Route Planning.  Computing and Informatics 31 (2012), 531--549.   URL: www.cai.sk/ojs/index.php/cai/article/view/1007.
• 2011 (co-author O. Moriš):   Scope-based route planning.  In: ESA 2011, Lecture Notes in Computer Science 6942, Springer (2011), 445--456.   URL: arxiv.org/abs/1101.3182. DOI 10.1007/978-3-642-23719-5_38. © Springer-Verlag.