Petr Hliněný

Welcome to my academic pages!

Scientific research - overview (read more)

• The theory research group - Discrete Methods and Algorithms (DIMEA), FI MU Brno, CZ,
  previously also Formal Methods, Logic and Algorithms (Formela).

• My research directions in brief (and current research news):
  • discrete mathematics, graph theory (structural and topological), discrete geometry,
  • theoretical computer science - combinatorial algorithms, parameterized complexity, logic.
• Current Ph.D. students (official listing): Filip Pokrývka (since 2019-), Shubhang Mittal (since 2023-), Jakub Balabán (since 2024-), Jan Jedelský (since 2024-).
• Selected past students: Robert Ganian (Ph.D. 2012) - now TU Wien,   Martin Derka (Mgr. 2013) - now at Quantstamp, Inc..   Jakub Gajarský (Ph.D. 2016) - now University of Warsaw.   Onur Cagirici (Ph.D. 2021) - now Novanta Inc., Deniz Agaoglu Cagirici (Ph.D. 2024) - now SAP,
• Collaborators - see the research page...
• Research opportunities for students (more details):
  • try the bonus assignments offered in IB000, and continue in my advanced seminars and courses;
  • e.g., attend the seminar FI:IV119 Seminar on Discrete Mathematical Methods (already for the second-year students),
  • see an offer of bachelor/master thesis topics (IS listing) related to my research, or come to ask to the FI:IV131 Seminar of Discrete Methods and Algorithms Laboratory, and also read about scientific achievements of my students,
  • consider the opportunity of a PhD study - with stipend (good foreign applicants welcome):
    

    Generally speaking, any theoretical research into graphs (with emphasis on structural and topological graph theory), into graph algorithms (with emphasis on parameterized complexity and logic on graphs), and some discrete geometrical problems can be discussed. See the current research topics.

• A short list of selected recent publications (full list):
  Petr Hliněný
  • 2024 (co-author A. Straka):   Stack and Queue Numbers of Graphs Revisited.  European J. Combinatorics (2025), to appear.   URL: arxiv.org/abs/2303.10116. © Elsevier B.V.
  • 2024:   Twin-width of Planar Graphs; a Short Proof.  European J. Combinatorics ? (2024), 104036.   URL: arxiv.org/abs/2302.08938. DOI 10.1016/j.ejc.2024.104036. © Elsevier B.V.
  • 2024 (co-authors M. Bekos, G. Da Lozzo, M. Kaufmann):   Graph Product Structure for h-Framed Graphs.  Electronic J. Combinatorics (2024), to appear.   URL: arxiv.org/abs/2204.11495.
  • 2024 (co-author J. Jedelský):   H-Clique-Width and a Hereditary Analogue of Product Structure.  In: MFCS, LIPiCS Vol. 306, Dagstuhl (2024), 61:1--61:16.   URL: arxiv.org/abs/2403.16789. DOI 10.4230/LIPIcs.MFCS.2024.61.
  • 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 T. Masařík):   Minimizing an Uncrossed Collection of Drawings.  In: Graph Drawing 2023, Proceedings, Lecture Notes in Computer Science 14465, Springer (2023), 110--123.   URL: arxiv.org/abs/2306.09550. DOI 10.1007/978-3-031-49272-3_8.
  • 2023 (co-authors B. Bergougnoux, J. Gajarský, G. Guspiel, F. Pokrývka, M. Sokolowski):   Sparse Graphs of Twin-width 2 Have Bounded Tree-width.  In: ISAAC 2023, LIPiCS Vol. 283, Dagstuhl (2023), 11:1--11:13.   URL: arxiv.org/abs/2307.01732. DOI 10.4230/LIPIcs.ISAAC.2023.11.
  • 2023 (co-author M. Chimani):   Inserting Multiple Edges into a Planar Graph.  Journal of Graph Algorithms and Applications 27 (2023), 489--522.   URL: arxiv.org/abs/1509.07952. DOI 10.7155/jgaa.00631.
  • 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.
  • 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-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.
  • 2022 (co-authors D. Bokal, Z. Dvořák, J. Leanos, B. Mohar, T. Wiedera):   Bounded degree conjecture holds precisely for c-crossing-critical graphs with c <= 12.  Combinatorica 42 (2022), 701--728.   URL: arxiv.org/abs/1903.05363. DOI 10.1007/s00493-021-4285-3.
  • 2022 (co-author T. Hamm):   Parameterised Partially-Predrawn Crossing Number.  In: 38th International Symposium on Computational Geometry (SoCG 2022), LIPIcs Vol. 224, Dagstuhl (2022), 46:1--46:15.   URL: arxiv.org/abs/2202.13635. DOI 10.4230/LIPIcs.SoCG.2022.46.
  • 2021 (co-authors J. Bok, J. Fiala, N. Jedličková, J. Kratochvíl):   Computational Complexity of Covering Two-vertex Multigraphs with Semi-edges.  In: Math Foundations of Computer Science MFCS 2021, LIPiCS Vol. 202, Dagstuhl (2021), 21:1--21:15.   URL: arxiv.org/abs/2103.15214. DOI 10.4230/LIPIcs.MFCS.2021.21.
  • 2021:   A Short Proof of Euler--Poincaré Formula.  In: Extended Abstracts EuroComb 2021, Trends in Mathematics, Springer (2021), 92--96.   URL: arxiv.org/abs/1612.01271. DOI 10.1007/978-3-030-83823-2_15.
  • 2020 (co-authors 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.
  • 2020 (co-author D. Agaoglu):   Isomorphism Problem for Sd-graphs.  In: Math Foundations of Computer Science MFCS 2020, LIPiCS Vol. 170, Dagstuhl (2020), 4:1--4:14.   URL: arxiv.org/abs/1907.01495. DOI 10.4230/LIPIcs.MFCS.2020.4.
  • 2020 (co-authors M. Chimani, G. Salazar):   Toroidal Grid Minors and Stretch in Embedded Graphs.  J. of Combinatorial Theory ser. B 140 (2020), 323--371.   URL: arxiv.org/abs/1403.1273. DOI 10.1016/j.jctb.2019.05.009. © Elsevier B.V.

Teaching and Academic matters (read more)

Petr Hliněný: official faculty personal page at FI MU Brno, CZ

• My courses (official info, - read more)
  • Autumn: "mass" course
    FI:IB000 Mathematical Foundations of CS, syllabus
    refer to this calendar for teaching hours, exams, etc.
  • Spring: graduate-level course
    FI:MA026 Advanced Combinatorics.
    Seminar group(s) of
    FI:IV119 Seminar on Discrete Mathematical Methods.
  • And an all-year-round research seminar group within
    FI:IV131 Seminar of Discrete Methods and Algorithms Laboratory.
• Guarantor of the Doctoral study programme Computer Science (the program board):
  • the one overall doctoral programme in all Computer Science at FI MU, Brno,
  • great opportunities for everybody wishing to study CS on the highest level, from pure theory to methodology and industrial applications.
• Once again, an offer of my Bc/Ms thesis topics,
• and numerous opportunities for students to join our theoretical research.

Teaching at FI

• IB000 MathCS  
• IV119 Semin.DM
• IV131 Seminar DIMEA

• Faculty page  
• Faculty management
• PhD Programme
• Supervised stud.
• Bc/Ms thesis topics

Math&CS research

• Topics
• Publications
• Recent results
• Google Scholar
• ResearcherID
• ORCID iD

• Research for stud.
• DIMEA
• D+F seminar

Flash news

• ISAAC'24, Sydney, Australia, December 8-11.
• Graph Drawing 2024, Vienna, Sep 18-20.
• GROW 2024, Cottbus, Sep 9-12.
• IPEC 2024 (ALGO), London, Sep 2-6.
• MFCS 2024, Bratislava, Aug 26-30.
• Crossing Numbers 2024, Montserrat, July 1-5.

My academic agenda

Masaryk University FI location

• Brno, Czech Republic

• FI MU buildings location