About my Math & CS scientific research
Prof. RNDr. Petr Hliněný, Ph.D.
@ynenilhfi.muni.cz
FI research group
Faculty of Informatics MU Brno, CZ
 Research contacs, 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, route planning, planar cover, Macek.
 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),
 Jan Obdržálek (FI), Bodhayan Roy (postdoc researcher 20172019), Michał Dębski (postdoc researcher 20182020).

Marek Derňár,
Onur Çağırıcı,
Deniz Agaoglu, Filip Pokrývka
(Ph.D. students).
New doctoral applicants are welcome, refer particularly to the current PhD calls with additional funding.  Michal Korbela, Tomáš Novotný (Master students).
 See also the DIMEA + Formela seminar, and the DIMEA lab (in past the Formela lab).
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 1700837S "Structural properties, parameterized tractability and hardness in combinatorial problems",
 now investigating 2004567S "Structure of tractable instances of hard algorithmic problems on graphs".
 Member  Institute of Theoretical Computer Science (ITI):
 Czech national project 1M0545, 20052011,
 then GAČR P202/12/G061, 20122018.
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 (COVID19!).
 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 (201820)
 Finally, finishing a full asymptotic characterization of ccrossingcritical graphs for fixed c>2. Joint work with Z. Dvořák and B. Mohar (SoCG2018). Then characterising the elusive case of ccrossingcritical 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 cliquewidth of point configurations (submitted).
 Conflictfree colour guarding of polygons  the vertextopoint 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 nonsimple (FSTTCS2017 and submitted improvement, with Cagirici and Roy).
 A short new proof of EulerPoincare 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; treewidth, branchwidth, rankwidth, DAGwidth, or DAGdepth, 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.
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: 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.
 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.
 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 depth measures (shrubdepth) 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 geometricallydefined graphs.
Key and/or recent publications: 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.
 2017 (coauthors 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 pathwidth. Random Structures & Algorithms 50 (2017), 612635. URL: arxiv.org/abs/1504.08122. DOI 10.1002/rsa.20676. © John Wiley & Sons, Inc.
 2016 (coauthors 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), 176184. DOI 10.1145/2933575.2935314. Preprint/file.
 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.
 2015 (coauthor 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/LMCS11(1:19)2015.
 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 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: 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.
 2019 (coauthors D. Bokal, Z. Dvořák, J. Leanos, B. Mohar, T. Wiedera): Bounded degree conjecture holds precisely for ccrossingcritical graphs with c <= 12. In: SoCG 2019, LIPIcs vol. 129, Dagstuhl (2019), 14:114:15. URL: arxiv.org/abs/1903.05363. DOI 10.4230/LIPIcs.SoCG.2019.14.
 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 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) cliquewidth to the order type of point configurations.
Key and/or recent publications: 2020 (coauthors O. Cagirici, F. Pokrývka, A. Sankaran): CliqueWidth of Point Configurations. In: GraphTheoretic Concepts in Computer Science, WG 2020, Lecture Notes in Computer Science ???, Springer (2020), to appear. URL: arxiv.org/abs/2004.02282.
 2020 (coauthors O. Cagirici, S.K. Ghosh, B. Roy): On conflictfree chromatic guarding of simple polygons. Submitted (2020), 26 p. URL: arxiv.org/abs/1904.08624.
 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.
 2017: A Short Proof of EulerPoincaré 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 projectiveplanar graphs. On the other hand, analogical conjecture about planar emulators was disproved in 2008 by RieckYamashita, and now we have got many more strange counterexamples to that. 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)
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: 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.