Petr Hliněný

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

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

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

• Petr Hliněný (team head),
  • Jan Obdržálek (researcher), Reshma Ramadurai (postdoc researcher 2011-2012),
  • Robert Ganian, Ondrej Moriš, Jakub Gajarský (Ph.D. students),
  • Matěj Klusáček, Martin Derka, Jozef Janovský, Marek Derňár (undergrads).
• New postdoc research position at FI MU Brno, CZ;
  available since 1.7.2012 for 3 years in the areas of Structural graph theory and Parameterized algorithms.
  • Salary about 55000 CZK per month. Must have received Ph.D. between 28.3.2008 - 1.7.2012, start by 1.9.2012, and be fluent in English. Teaching load around 3-5 hours per week (quite mild).
  • Apply by 31.3.2012. Application information on this page.
• See also the FMDSA working seminar.

Collaboration with other Czech universities:

• Charles University, MFF (Prague)
  • Jan Kratochvíl, GraDR - EuroGIGA - read below...
  • Dan Kráľ and Zdeněk Dvořák - see also their CCOSA project,
    collaborating on structural graph problems, and on crossing numbers.
• West Bohemia University, FAV (Pilsen)
  • Dan Kráľ (again) and Jakub Teska, GAČR P202/11/0196 - read below...

Collaboration with foreign institutions:

• RWTH Aachen University, Germany
  • Peter Rossmanith, Theoretical Computer Science,
    jointly working mainly on structural width parameters and parameterized algorithmics.
• University Jena, Germany
  • Markus Chimani, Algorithm Engineering,
    graph crossing number algorithms, and topological graph problems.
• Universidad Autonoma de San Luis Potosi, Mexico
  • Gelasio Salazar, Instituto de Física,
    graph crossing numbers, and topological graph problems.

• Czech Science Foundation (GAČR):
  • 3 research grants successfully finished prior to 2011,
  • now leading P202/11/0196 "Well-structured combinatorial classes, width parameters, and design of efficient algorithms", co-investigator Dan Kráľ.
• EuroGIGA project  Graph Drawings and Representations:
  • 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, 2005-2011,
  • now GAČR P202/12/G061, 2012-2018.

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 (with emphasis on parameterized complexity) can be discussed for a PhD.
  • Refer to the admission procedure.
• 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.

Student 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! Even first year students with interest in math are most warmly welcome.

• Official seminar entry in IS
• Spring 2012 seminar: every Tuesday 10-12h, now in G123 (Gotex).
  • Want to think about some nice combinatorial problems...?
    OK, so how many balls can touch each other in 3D? 5 or 6?
    And how many convex polytopes may touch (face-to-face) each other in 3D? 10 or 100, or even more?
  • Come and see us!

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, DAG-width, or DAG-depth, 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.

Our recent research directions include special emphasis on directed graph width measures, especially on bi-rank-width, and on getting complexity lower bounds on tractability wrt. width parameters.

• 2012 (co-authors R. Ganian, J. Obdržálek, J. Nešetřil, P. Ossona de Mendez, R. Ramadurai):   When Trees Grow Low: Shrubs and Fast MSO1.  Submitted (2012), 22 p.
• 2011 (co-authors R. Ganian, J. Obdržálek):   Clique-width: When Hard Does Not Mean Impossible.  In: STACS 2011, Leibniz International Proceedings in Informatics LIPIcs Vol 9, Dagstuhl (2011), 404-415.   URL: drops.dagstuhl.de/opus/volltexte/2011/3030. DOI 10.4230/LIPIcs.STACS.2011.404.
• 2010 (co-authors R. Ganian, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar):   Are there any good digraph width measures?.  In: IPEC 2010, Lecture Notes in Computer Science 6478, Springer Verlag (2010), 135-146.   URL: arxiv.org/abs/1004.1485v1. DOI 10.1007/978-3-642-17493-3_14. © Springer-Verlag.
• 2009 (co-authors R. Ganian, J. Kneis, A. Langer, J. Obdržálek, P. Rossmanith):   On Digraph Width Measures in Parameterized Algorithmics (extended abstract).  In: IWPEC 2009, Lecture Notes in Computer Science 5917, Springer (2009), 185-197.   DOI 10.1007/978-3-642-11269-0_15. © Springer-Verlag. Preprint/file.
• 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.
• 2008 (co-authors S. Oum, D. Seese, G. Gottlob):   Width Parameters Beyond Tree-width and Their Applications.  Invited survey paper, Computer Journal 51 (2008), 326-362.   DOI 10.1093/comjnl/bxm052. © Oxford University Press. Preprint/file.
• 2006 (co-author G. Whittle):   Matroid Tree-Width.  Europ. J. Combin. 27 (2006), 1117-1128.   DOI 10.1016/j.ejc.2006.06.005. © Elsevier B.V. Preprint/file. Addendum.

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. The question of what are the limits (lower bounds) of this approach is also considered.

• 2012 (co-author J. Gajarský):   MSO Model Checking of Graphs: Has it all been told already?.  Submitted (2012), 16 p.   URL: arxiv.org/abs/1204.5194.
• 2012 (co-authors R. Ganian, A. Langer, J. Obdržálek, P. Rossmanith, S. Sikdar):   Lower Bounds on the Complexity of MSO1 Model-Checking.  In: STACS 2012, Leibniz International Proceedings in Informatics LIPIcs, Dagstuhl (2012), 326-337.   URL: arxiv.org/abs/1109.5804. DOI 10.4230/LIPIcs.STACS.2012.326.
• 2006:   Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids.  J. of Combinatorial Theory ser. B 96 (2006), 325-351.   DOI 10.1016/j.jctb.2005.08.005. © Elsevier B.V. Preprint/file.

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

• 2011 (co-author M. Chimani):   A Tighter Insertion-based Approximation of the Crossing Number.  In: ICALP 2011, Part I, Lecture Notes in Computer Science 6755, Springer (2011), 122-134.   DOI 10.1007/978-3-642-22006-7_11. © Springer-Verlag. Preprint/file.
• 2010 (co-author M. Chimani):   Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface.  In: 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.
• 2003:   Crossing-Number Critical Graphs have Bounded Path-Width.  J. of Combinatorial Theory ser. B 88 (2003), 347-367.   DOI 10.1016/S0095-8956(03)00037-6. © Elsevier B.V. Preprint/file.

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

• 2012 (co-author O. Moriš):   Generalized Maneuvers in Route Planning.  Computing and Informatics (2012), to appear, 18 p.   URL: arxiv.org/abs/1107.0798.
• 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.

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 projective-planar graphs. On the other hand, analogical conjecture about planar emulators was disproved in 2008 by Rieck-Yamashita, and now we have got many more strange counterexamples to that. Both these problems are still wide open.

• 2012 (co-authors M. Chimani, M. Derka, M. Klusáček):   How Not to Characterize Planar-emulable Graphs.  Advances in Applied Mathematics (2012), to appear, 26 p.   URL: arxiv.org/abs/1107.0176.
• 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.
• 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.
• 1999:   Planar covers of graphs: Negami's conjecture.  PhD. Dissertation, School of Math., Georgia Institute of Technology (1999), 132 p.   Preprint/file.