Welcome to my academic pages!
Prof. RNDr. Petr Hliněný, Ph.D.
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): Marek Derňár (since 2012- unfinished?). Onur Cagirici (since 2016-), 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.
- 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
- 2020 (co-author D. Agaoglu): Isomorphism Problem for Sd-graphs. In: Math Foundations of Computer Science MFCS 2020, LIPiCS, Dagstuhl (2020), to appear. URL: arxiv.org/abs/1907.01495.
- 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 (2020), to appear. URL: arxiv.org/abs/1805.01823.
- 2020 (co-authors O. Cagirici, F. Pokrývka, A. Sankaran): Clique-Width of Point Configurations. In: Graph-Theoretic Concepts in Computer Science, WG 2020, Lecture Notes in Computer Science ???, Springer (2020), to appear. URL: arxiv.org/abs/2004.02282.
- 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.05363. 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, -
- 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).
- Autumn: "mass" courses
- Study programme of Mathematical Informatics
- 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.