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,
  past 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): Deniz Agaoglu (since 2018-), Filip Pokrývka (since 2019-).
• 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 Ryerson University..
• Collaborators - see the research page...
• Research opportunities for students (more details):
  • try those various bonus assignments offered in my mass courses, and continue in my advanced courses,
  • visit the seminar FI:IV119 Seminar on Discrete Mathematical Methods (already for first-year students),
  • try those various bonus assignments offered in my mass courses, and continue in my advanced seminars, see here,
  • see an offer of bachelor/master thesis topics related to my research (IS listing),
    and 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ý
  • 2022 (co-author J. Jedelský):   Twin-width of Planar Graphs is at most 8, and at most 6 when Bipartite Planar.  Preprint (2022), 19 p.   URL: arxiv.org/abs/2210.08620.
  • 2022:   Twin-width of Planar Graphs is at most 9, and at most 6 when Bipartite Planar.  Preprint (2022), 18 p.   URL: arxiv.org/abs/2205.05378.
  • 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-authors M. Bekos, G. Da Lozzo, M. Kaufmann):   Graph Product Structure for h-Framed Graphs.  In: ISAAC 2022, LIPIcs Vol. 248, Dagstuhl (2022), 23:1--23:15.   URL: arxiv.org/abs/2204.11495. DOI 10.4230/LIPIcs.ISAAC.2022.23.
  • 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.
  • 2019 (co-authors 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.
  • 2019 (co-author A. Sankaran):   Exact Crossing Number Parameterized by Vertex Cover.  In: Graph Drawing 2019, Lecture Notes in Computer Science 11904, Springer (2019), 307--319.   URL: arxiv.org/abs/1906.06048. DOI 10.1007/978-3-030-35802-0_24.
  • 2019 (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.  In: SoCG 2019, LIPIcs vol. 129, Dagstuhl (2019), 14:1--14:15.   URL: arxiv.org/abs/1903.05363v1. DOI 10.4230/LIPIcs.SoCG.2019.14.
  • 2019 (co-authors M.Bračič, D. Bokal, M. Derňár):   On Degree Properties of Crossing-critical Families of Graphs.  Electr. Journal of Combinatorics 26 (2019), #P1.53.   URL: www.combinatorics.org/ojs/index.php/eljc/article/view/v26i1p53/7812. DOI 10.37236/7753.
  • 2019 (co-authors R. Ganian, J. Nešetřil, J. Obdržálek, P. Ossona de Mendez):   Shrub-depth: Capturing Height of Dense Graphs.  Logical Methods in Computer Science 15 (2019), 7:1--7:25.   URL: arxiv.org/abs/1707.00359. DOI 10.23638/LMCS-15(1:7)2019.
  • 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.
  • 2019 (co-authors J. Gajarský, M. Koutecký, S. Onn):   Parameterized Shifted Combinatorial Optimization.  Journal of Computer and System Sciences 99 (2019), 53--71.   URL: arxiv.org/abs/1702.06844. DOI 10.1016/j.jcss.2018.06.002. © Elsevier B.V.
  • 2018 (co-authors J. Gajarský, H.R. Tiwary):   Parameterized Extension Complexity of Independent Set and Related Problems.  Discrete Applied Mathematics 248 (2018), 56--67.   URL: arxiv.org/abs/1511.08841. DOI 10.1016/j.dam.2017.04.042. © Elsevier B.V.
  • 2018 (co-author C. Thomassen):   Deciding Parity of Graph Crossing Number.  SIAM J. Discrete Mathematics 32-3 (2018), 1962--1965.   DOI 10.1137/17M1137231. © Society for Industrial and Applied Mathematics. Preprint/file.
  • 2018:   Simpler Self-reduction Algorithm for Matroid Path-width.  SIAM J. Discrete Mathematics 32-2 (2018), 1425-1440.   URL: arxiv.org/abs/1605.09520. DOI 10.1137/17M1120129. © Society for Industrial and Applied Mathematics.
  • 2018 (co-authors Z. Dvořák, B. Mohar):   Structure and generation of crossing-critical graphs.  In: SoCG 2018, LIPIcs Vol. 99, Dagstuhl (2018), 33:1--33:14.   URL: arxiv.org/abs/1803.01931. DOI 10.4230/LIPIcs.SoCG.2018.33.
  • 2017 (co-authors 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 path-width.  Random Structures & Algorithms 50 (2017), 612--635.   URL: arxiv.org/abs/1504.08122. DOI 10.1002/rsa.20676. © John Wiley & Sons, Inc.
  • 2017 (co-author M. Chimani):   A Tighter Insertion-based Approximation of the Crossing Number.  Journal of Combinatorial Optimization 33 (2017), 1183--1225.   URL: arxiv.org/abs/1104.5039. DOI 10.1007/s10878-016-0030-z. © Elsevier B.V.
  • 2017 (co-authors 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), 219--242.   URL: arxiv.org/abs/1302.6863. DOI 10.1016/j.jcss.2016.09.002. © 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" courses
    FI:MA010 Graph Theory, syllabus
    FI:IB000 Mathematical Foundations of CS, syllabus
    refer to this calendar for teaching hours, exams, etc.
  • Spring: selective seminar groups in
    FI:IV125 Formela lab seminar (see in IS)
    and an offer for interested young students
    FI:IV119 Seminar on Discrete Mathematical Methods (in IS).
• Study programme of Mathematical Informatics (official info):
  • bachelor degree program offered for students who want to know more on mathematical background of Computer Science, and who would, perhaps, like to continue an academic career in theoretical CS,
  • great opportunities for theory research are offered to students already at the Bachelor level, among others within our research group.
• Once again, an offer of my Bc/Ms thesis topics,
• possibility of a PhD study at FI MU Brno, CZ - with stipend,
• and numerous opportunities for students to join our theoretical research.

Teaching at FI

• MA010 Graph  
• IB000 MathCS  
• Advanced courses

• 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

• Graph Drawing 2023, Palermo, Italy, Sep 20-22
• Eurocomb'23, Prague, Aug 28 - Sep 1.
• Crossing Numbers 2023, Rogla, July 10-14.
• New Frontiers of Parameterized Complexity in Graph Drawing, Dagstuhl, April 16-21, 2023

My academic agenda

Masaryk University FI location

• Brno, Czech Republic

• FI MU buildings location