Petr Hliněný

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

@ynenilhfi.muni.cz
Faculty of Informatics MU Brno, CZ
Office C418 in the FI building, 4th floor
Calendar of my teaching, exams, office hours

• Courses: "mass" IB000 (see in IS IB000),
• and further advanced courses and seminars (IV119, MA026, IV131).
• Selection of Bc/Ms thesis topics.
• Recent student achievements.

Generally, any chosen sufficiently interesting topic of graph theory or related algorithmic questions, including parameterized complexity, or combinatorial geometry, may be taken for thesis under my supervision - based on prior mutual agreement. The preference is for topics doing a least a bit of scientific research, and written up in English.

• Officially listed (generic) Bachelor thesis topic.
• For the master level, you may browse under my name the whole list of Master thesis topics.
  
  • The topics include, e.g, studying width parameters and related games, computing the decompositions, designing parameterized algorithms on graphs, studying crossing number questions, the practical route-planning problem, etc...
• Selected most successful past thesis titles:
  
  • Twin-width of planar graphs, Computing twin-width parametrized by restrictive parameters, Stack number and queue number of graphs, Constructive twin-width for posets of small width, Crossing-critical graphs of high vertex degrees, FO properties of geometric graphs, Obstructions for graphs of low rank-depth, Efficient solvability of graph MSO properties, Partitioning of Weighted Graphs into k Connected Subgraphs, Construction of planar emulators of graphs, Efficient route-planning in huge graphs, Planar graph emulators: Fellows' conjecture, Automata-formalization for graphs of bounded rank-width...
• A list of my all supervised students at FI MU Brno, CZ.
• See also the current research directions and results of my group.

Read about  Ph.D. study in my group

• Rector's Awards MU:
  J. Gajarský, 2016 Rector's Award for the Best Students in Doctoral Programmes,
  J. Gajarský, 2017 Rector's Award for an Outstanding Doctoral Thesis.
• Undergraduate student scientific competition SVOČ (in Math&CS):
  1st prizes R. Ganian (2008), J. Balabán and J. Jedelský (2022)
  2nd prizes O. Moriš (2008), M. Derka (2010), M. Klusáček (2011), J. Gajarský (2012), M. Bezek (2016).
• Best student papers of:
  SOFSEM 2011 (R. Ganian), MEMICS 2011 (O. Moriš), CSR 2020 (O. Cagirici).
• Selected publication coauthored with my students:
  • 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.
  • 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-author D. Agaoglu Cagirici):   Efficient Isomorphism for Sd-graphs and T-graphs.  Algorithmica 85 (2023), 352--383.   URL: arxiv.org/abs/1907.01495. DOI 10.1007/s00453-022-01033-8.
  • 2023 (co-author A. Straka):   Stack and Queue Numbers of Graphs Revisited.  In: Eurocomb'23, Proceedings, Masaryk University Press (2023), 601--606.   URL: arxiv.org/abs/2303.10116. DOI 10.5817/CZ.MUNI.EUROCOMB23-083.
  • 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.
  • 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 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.
  • 2016 (co-authors 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), 176--184.   DOI 10.1145/2933575.2935314. Preprint/file.
  • 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.
  • 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.