About my Math & CS scientific research
Prof. RNDr. Petr Hliněný, Ph.D.
@ynenilhfi.muni.cz
FI research group DIMEA
Faculty of Informatics MU Brno, CZ
 Research collaborators, and grants.
 Recent results (obtained by our group).
 Research opportunities for students in our group.
 Research topics: width params, logic alg, crossing number, geometric graphs, planar cover,
 See also the complete publication and conference lists.
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 20232024).

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 2004567S "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 researchoriented 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 (202023)
 Following the asymptotic characterization of ccrossingcritical graphs for fixed c>2, obtained exact characterization of when ccrossingcritical 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 cliquewidth of point sets  configurations (with O.Cagirici, F. Pokrývka and A. Sankaran, JCTB 2023).
 A short new proof of EulerPoincare Formula in every dimension, not using shellability of polytopes (EuroComb 2021).
 Efficient isomorphism for intersection graphs  FPT for Sdgraphs and Tgraphs, and ongoing research towards Hgraphs with unicyclic H (with D. Agaoglu Cagirici, Algorithmica 2023 ++), while this problem is GIhard for all H having at least two cycles.
 Twinwidth 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; treewidth, branchwidth, rankwidth, shrubdepth, or new twinwidth, 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 MSOdefinable properties. The question of how to obtain such low degree structural decompositions is also studied, e.g. obtaining matroid branchdecomposition and graph rankdecomposition in FPT.
Key and/or recent publications: 2023: Twinwidth of Planar Graphs; a Short Proof. Eurocomb'23 (2023), to appear. URL: arxiv.org/abs/2302.08938.
 2023 (coauthor J. Jedelský): Twinwidth of Planar Graphs is at most 8, and at most 6 when Bipartite Planar. In: ICALP 2023 (2023), to appear. URL: arxiv.org/abs/2210.08620.
 2019 (coauthors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez): Shrubdepth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15 (2019), 7:17:25. URL: arxiv.org/abs/1707.00359. DOI 10.23638/LMCS15(1:7)2019.
 2019 (coauthors J. Gajarský, M. Koutecký, S. Onn): Parameterized Shifted Combinatorial Optimization. Journal of Computer and System Sciences 99 (2019), 5371. URL: arxiv.org/abs/1702.06844. DOI 10.1016/j.jcss.2018.06.002. © Elsevier B.V.
 2018: Simpler Selfreduction Algorithm for Matroid Pathwidth. SIAM J. Discrete Mathematics 322 (2018), 14251440. URL: arxiv.org/abs/1605.09520. DOI 10.1137/17M1120129. © Society for Industrial and Applied Mathematics.
 2017 (coauthors 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), 219242. URL: arxiv.org/abs/1302.6863. DOI 10.1016/j.jcss.2016.09.002. © Elsevier B.V.
 2016 (coauthors 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), 250286. URL: arxiv.org/abs/1004.1485. DOI 10.1016/j.jctb.2015.09.001. © Elsevier B.V.
 2016 (coauthors O. Kwon, J. Obdržálek, S. Ordyniak): Treedepth and Vertexminors. European J. Combinatorics 56 (2016), 4656. URL: arxiv.org/abs/1403.7024. DOI 10.1016/j.ejc.2016.03.001. © Elsevier B.V.
 2008 (coauthor S. Oum): Finding Branchdecompositions and Rankdecompositions. SIAM J. Computing 38 (2008), 10121032. DOI 10.1137/070685920. © Society for Industrial and Applied Mathematics. Preprint/file.
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 (shrubdepth, newly twinwidth) 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 (coauthors O. Cagirici, F. Pokrývka, A. Sankaran): CliqueWidth of Point Configurations. J. of Combinatorial Theory ser. B 158 (2023), 4373. URL: arxiv.org/abs/2004.02282. DOI 10.1016/j.jctb.2021.09.001.
 2022 (coauthors J. Balabán, J. Jedelský): Twinwidth and Transductions of Proper kMixedThin Graphs. In: GraphTheoretic Concepts in Computer Science, WG 2022, Lecture Notes in Computer Science 13453, Springer (2022), 4355. URL: arxiv.org/abs/2202.12536. DOI 10.1007/9783031159145_4.
 2020 (coauthors 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 (coauthors F. Pokrývka, B. Roy): FO model checking of geometric graphs. Computational Geometry: Theory and Applications 78 (2019), 119. URL: arxiv.org/abs/1709.03701. DOI 10.1016/j.comgeo.2018.10.001. © Elsevier B.V.
 2019 (coauthors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez): Shrubdepth: Capturing Height of Dense Graphs. Logical Methods in Computer Science 15 (2019), 7:17:25. URL: arxiv.org/abs/1707.00359. DOI 10.23638/LMCS15(1:7)2019.
 2015 (coauthors 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), 963974. URL: arxiv.org/abs/1504.04115. DOI 10.1109/FOCS.2015.63.
 2014 (coauthors R. Ganian, A. Langer, J. Obdržálek, P. Rossmanith, S. Sikdar): Lower Bounds on the Complexity of MSO1 ModelChecking. Journal of Computer and System Sciences 80 (2014), 180194. URL: arxiv.org/abs/1109.5804. DOI 10.1016/j.jcss.2013.07.005. © Elsevier B.V.
 2012 (coauthors 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), 419430. DOI 10.1007/9783642325892_38. © SpringerVerlag. 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 crossingcritical graphs, and with computational hardness questions related to this problem. We are now particularly looking at an approximate structural description of crossingcritical graphs, and on strengthening known algorithmic and hardness results on very special classes of graphs.
Key and/or recent publications: 2022 (coauthors D. Bokal, Z. Dvořák, J. Leanos, B. Mohar, T. Wiedera): Bounded degree conjecture holds precisely for ccrossingcritical graphs with c <= 12. Combinatorica 42 (2022), 701728. URL: arxiv.org/abs/1903.05363. DOI 10.1007/s0049302142853.
 2022 (coauthor T. Hamm): PartiallyPredrawn Crossing Number and the Critical Graphs. Preprint (2022), 21 p.
 2020 (coauthors M. Chimani, G. Salazar): Toroidal Grid Minors and Stretch in Embedded Graphs. J. of Combinatorial Theory ser. B 140 (2020), 323371. URL: arxiv.org/abs/1403.1273. DOI 10.1016/j.jctb.2019.05.009. © Elsevier B.V.
 2019 (coauthor A. Sankaran): Exact Crossing Number Parameterized by Vertex Cover. In: Graph Drawing 2019, Lecture Notes in Computer Science 11904, Springer (2019), 307319. URL: arxiv.org/abs/1906.06048. DOI 10.1007/9783030358020_24.
 2018 (coauthors Z. Dvořák, B. Mohar): Structure and generation of crossingcritical graphs. In: SoCG 2018, LIPIcs Vol. 99, Dagstuhl (2018), 33:133:14. URL: arxiv.org/abs/1803.01931. DOI 10.4230/LIPIcs.SoCG.2018.33.
 2018 (coauthor C. Thomassen): Deciding Parity of Graph Crossing Number. SIAM J. Discrete Mathematics 323 (2018), 19621965. DOI 10.1137/17M1137231. © Society for Industrial and Applied Mathematics. Preprint/file.
 2017 (coauthor M. Chimani): A Tighter Insertionbased Approximation of the Crossing Number. Journal of Combinatorial Optimization 33 (2017), 11831225. URL: arxiv.org/abs/1104.5039. DOI 10.1007/s108780160030z. © Elsevier B.V.
 2016 (coauthor M. Derňár): Crossing Number is Hard for Kernelization. In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 42:142:10. URL: arxiv.org/abs/1512.02379. DOI 10.4230/LIPIcs.SoCG.2016.42.
 2016 (coauthor M. Chimani): Inserting Multiple Edges into a Planar Graph. In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 30:130:15. URL: arxiv.org/abs/1509.07952. DOI 10.4230/LIPIcs.SoCG.2016.30.
 2010 (coauthor M. Chimani): Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. In: Symposium on Discrete Algorithms SODA 2010, ACMSIAM (2010), 918927. URL: www.siam.org/proceedings/soda/2010/soda10.php. © Society for Industrial and Applied Mathematics. Preprint/file.
 2010 (coauthor G. Salazar): Stars and Bonds in CrossingCritical Graphs. Journal of Graph Theory 65 (2010), 198215. 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), 455471. DOI 10.1016/j.jctb.2005.09.009. © Elsevier B.V. Preprint/file.
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 Hgraphs. A related new direction is that extending the notion of (graph) cliquewidth to the order type of point configurations.
Key and/or recent publications: 2023 (coauthors O. Cagirici, F. Pokrývka, A. Sankaran): CliqueWidth of Point Configurations. J. of Combinatorial Theory ser. B 158 (2023), 4373. URL: arxiv.org/abs/2004.02282. DOI 10.1016/j.jctb.2021.09.001.
 2021: A Short Proof of EulerPoincaré Formula. In: Extended Abstracts EuroComb 2021, Trends in Mathematics, Springer (2021), 9296. URL: arxiv.org/abs/1612.01271. DOI 10.1007/9783030838232_15.
 2019 (coauthors O. Cagirici, S.K. Ghosh, B. Roy): On conflictfree chromatic guarding of simple polygons. In: COCOA 2019, Lecture Notes in Computer Science 11949, Springer (2019), 601612. URL: arxiv.org/abs/1904.08624. DOI 10.1007/9783030364120_49.
 2019 (coauthors F. Pokrývka, B. Roy): FO model checking of geometric graphs. Computational Geometry: Theory and Applications 78 (2019), 119. URL: arxiv.org/abs/1709.03701. DOI 10.1016/j.comgeo.2018.10.001. © Elsevier B.V.
 2018 (coauthors O. Cagirici, B. Roy): On Colourability of Polygon Visibility Graphs. In: FSTTCS 2017, LIPIcs Vol. 93, Dagstuhl (2018), 21:121:14. DOI 10.4230/LIPIcs.FSTTCS.2017.21.
 2001: An Addition to Art Galleries with Interior Walls. Discrete Computational Geometry 25 (2001), 311314. DOI 10.1007/s004540010078.
 1998: Classes and recognition of curve contact graphs. J. of Combinatorial Theory ser. B 74 (1998), 87103. DOI 10.1006/jctb.1998.1846. © Elsevier B.V. Preprint/file.
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 projectiveplanar graphs. On the other hand, analogical conjecture about planar emulators was disproved in 2008 by RieckYamashita, and we have got many more strange counterexamples to that. Definite answers to both these problems are still wide open.
Key publications: 2015 (coauthor M. Derka): Planar Emulators Conjecture Is Nearly True for Cubic Graphs. European J. Combinatorics 48 (2015), 6370. DOI 10.1016/j.ejc.2015.02.009. © Elsevier B.V. Preprint/file.
 2013 (coauthors M. Chimani, M. Derka, M. Klusáček): How Not to Characterize Planaremulable Graphs. Advances in Applied Mathematics 50 (2013), 4668. 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), 525536. DOI 10.1007/s0037301009349. © SpringerVerlag. Preprint/file. Addendum.
 2004 (coauthor R. Thomas): On possible counterexamples to Negami's planar cover conjecture. Journal of Graph Theory 46 (2004), 183206. 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.
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: 2019 (coauthors 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 (coauthor O. Moriš): Generalized Maneuvers in Route Planning. Computing and Informatics 31 (2012), 531549. URL: www.cai.sk/ojs/index.php/cai/article/view/1007.
 2011 (coauthor O. Moriš): Scopebased route planning. In: ESA 2011, Lecture Notes in Computer Science 6942, Springer (2011), 445456. URL: arxiv.org/abs/1101.3182. DOI 10.1007/9783642237195_38. © SpringerVerlag.