About my Math & CS scientific research
Prof. RNDr. Petr Hliněný, Ph.D.
@ynenilhfi.muni.cz
FI research direction
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, route planning, planar cover.
 MACEK  practical structural computation with matroids.
 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 collaboration
Local research team at Faculty of Informatics MU Brno, CZ:
 Petr Hliněný (team head),
 Jan Obdržálek
(researcher), Alexandru
Popa (faculty till 2014),
Reshma Ramadurai (postdoc researcher 20112013), Sebastian Ordyniak (postdoc researcher 20122015), Michal Kotrbčík (postdoc researcher 20132015), the postdoc EU project at MU.  Jakub Gajarský, Marek Derňár, Onur Çağırıcı (Ph.D. students).
 New doctoral applicants are welcome, refer particularly to the current PhD calls with additional funding.
 Jan Obdržálek
(researcher), Alexandru
Popa (faculty till 2014),
 See also the FMDSA working seminar, and the ITI centre.
Collaboration with other Czech universities:
 Charles University, MFF (Prague)
 Jan Kratochvíl, GraDR  EuroGIGA  read below..., Zdeněk Dvořák
 Dan Kráľ (now Warwick) and
collaborating on structural graph problems, and on crossing numbers.
 West Bohemia University, FAV (Pilsen)
 Tomáš Kaiser and Jakub Teska, GAČR P202/11/0196  during 20112014.
Collaboration with foreign institutions:
 University of Warwick, UK
 Daniel Kráľ, Mathematics Institute,
topics related to algorithmic metatheorems and graph limits.
 Daniel Kráľ, Mathematics Institute,
 RWTH Aachen University, Germany
 Peter Rossmanith et al, Theoretical Computer Science,
jointly working mainly on structural width parameters and parameterized algorithmics.
 Peter Rossmanith et al, Theoretical Computer Science,
 University of Bergen, Norway
 Saket Saurabh, Daniel Lokshtanov, Informatics,
algorithmic metatheorems and logic on graphs.
 Saket Saurabh, Daniel Lokshtanov, Informatics,
 University Osnabrueck, Germany
 Markus Chimani, Theoretical
Computer Science,
graph crossing number algorithms, and topological graph problems.
 Markus Chimani, Theoretical
Computer Science,
 Universidad Autonoma de San Luis Potosi, Mexico
 Gelasio Salazar, Instituto de Física,
graph crossing numbers, and topological graph problems.
 Gelasio Salazar, Instituto de Física,
Current research grants
 Czech Science Foundation (GAČR):
 5 research grants successfully finished prior to 2015,
 now investigating 1700837S "Structural properties, parameterized tractability and hardness in combinatorial problems"
 EuroGIGA project
Graph Drawings and Representations
(201114):
 EUROCORES collaborative research project of 7 countries,
 work package "WP08 Crossing number" centered at FI MU Brno, CZ.
 Institute of Theoretical Computer Science (ITI):
 Czech national project 1M0545, 20052011,
 now 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 Spring School on Combinatorics organized every year by KAM MFF UK, or at the SVOČ student scientific competition.
Formela Lab 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 2017 seminar: in C417, Wednesday 810 every week
 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...

For every interested students, think about the following already before the first seminar:
What Euler's formula says for a polytope in 4D? How to prove it, knowing the 3D version?
Alternatively: Imagine a simplex in 3D, and several (or many) points inside it. Can you now cut the big simplex into smaller simplices such that their vertices will be the original vertices or the given internal points, and that every two of these points will share an edge of some simplex? (I.e., the net of this complex shall be the complete graph.) How would you describe such a cutting?  Come and see us (even if you participated in 2016  we will study different topics of The Book)...
 See also a list of past 2016 topics here.
Recent results and ongoing research (20157)
 A short new proof of EulerPoincare Formula in every dimension, not using shellability of polytopes.
 Algorithmic metatheorems for FO logic on dense structures  an FPT m.c. algorithm on posets of bounded width (FOCS2015), a new perspective on interpretation of dense classes into sparse classes (LICS2016); with local Brno collaborators and people from Bergen. See below.
 A selfreduction FPT algorithm for matroid pathdecomposition, linear rankdecomposition of a graph, and Trellis decomposition of a linear code. Simpler than the SODA2016 algorithm of Oum et al.
 New hardness results for the graph crossing number problems  hardness of joint embedding in genus 6, hardness of the crossing number for almostplanar graphs even if no more than 16 vertices have degree >3 (both ISAAC2015), no polynomial kernel for crossing number (SoCG2016), and more... Partly with G. Salazar, M. Dernar.
 The multipleedge insertion problem in planar graphs is solvable exactly in parameterized linear time (before, only constant additive factor approximation known in full linear time). With M. Chimani (SoCG2016).
 Towards an asymptotic characterization of kcrossingcritical graphs for fixed k>2:
Those have bounded dual diameter, and much more in their structure...; with Z. Dvořák and L. Postle, and still in very early development.  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 recent publications: 2017 (coauthors J. Gajarský, H.R. Tiwary): Parameterized Extension Complexity of Independent Set and Related Problems. Discrete Applied Mathematics (2017), to appear. URL: arxiv.org/abs/1511.08841.
 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.
 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.
 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.
 2013 (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. In: ESA 2013, Lecture Notes in Computer Science 8125, Springer (2013), 529540. URL: arxiv.org/abs/1302.6863. DOI 10.1007/9783642404504_45. © SpringerVerlag.
 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.
 2011 (coauthors R. Ganian, J. Obdržálek): Cliquewidth: When Hard Does Not Mean Impossible. In: Symposium on Theoretical Aspects of Computer Science STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl (2011), 404415. URL: drops.dagstuhl.de/opus/volltexte/2011/3030. DOI 10.4230/LIPIcs.STACS.2011.404.
 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 in 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.
Recent important results have been obtained for FO properties on posets of bounded width (meaning the size of a largest antichain).
Key publications: 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.
 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 (2017), to appear. URL: arxiv.org/abs/1504.08122. DOI 10.1002/rsa.20676. © John Wiley & Sons, Inc.
 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 (coauthors J. Gajarský, J. Obdržálek, S. Ordyniak): Faster Existential FO Model Checking on Posets. Logical Methods in Computer Science 11(4) (2015), paper 8. URL: arxiv.org/abs/1409.4433. DOI 10.2168/LMCS11(4:8)2015.
 2015 (coauthors R. Ganian, D. Král', J. Obdržálek, J. Schwartz, J. Teska): FO Model Checking of Interval Graphs. Logical Methods in Computer Science 11(4) (2015), paper 11. URL: arxiv.org/abs/1302.6043. DOI 10.2168/LMCS11(4:11)2015.
 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.
 2006: BranchWidth, Parse Trees, and Monadic SecondOrder Logic for Matroids. J. of Combinatorial Theory ser. B 96 (2006), 325351. DOI 10.1016/j.jctb.2005.08.005. © Elsevier B.V. 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 hardness results on very special classes of graphs.
Key publications: 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.
 2015 (coauthor G. Salazar): On Hardness of the Joint Crossing Number. In: ISAAC 2015, Lecture Notes in Computer Science 9472, Springer (2015), 603613. URL: arxiv.org/abs/1509.01787. DOI 10.1007/9783662489710_51.
 2014 (coauthors M. Chimani, G. Salazar): Toroidal Grid Minors and Stretch in Embedded Graphs. Submitted (2014), 40 p. URL: arxiv.org/abs/1403.1273.
 2011 (coauthor M. Chimani): A Tighter Insertionbased Approximation of the Crossing Number. In: ICALP 2011, Part I, Lecture Notes in Computer Science 6755, Springer (2011), 122134. DOI 10.1007/9783642220067_11. © SpringerVerlag.
 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.
 2003: CrossingNumber Critical Graphs have Bounded PathWidth. J. of Combinatorial Theory ser. B 88 (2003), 347367. DOI 10.1016/S00958956(03)000376. © Elsevier B.V. Preprint/file.
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: 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.