Welcome to my academic pages!
Prof. RNDr. Petr Hliněný, Ph.D.
Scientific research - overview (read more)
- The theory research group - Formal Methods, Logic and
FI MU Brno, CZ,
and the official research topics.
- 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-). Onur Cagirici (since 2016-).
- Selected past students: Robert Ganian (Ph.D. 2012) - now TU Wien, Martin Derka (Mgr. 2013) - now Univ. Waterloo. Jakub Gajarský (Ph.D. 2016), - now TU Berlin.
- 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 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
- 2017: A Short Proof of Euler-Poincaré Formula. manuscript (2017), 5 p. URL: arxiv.org/abs/1612.01271.
- 2018 (co-author C. Thomassen): Deciding Parity of Graph Crossing Number. SIAM J. Discrete Mathematics (2018?), to appear. © Society for Industrial and Applied Mathematics. Preprint/file.
- 2018: Simpler Self-reduction Algorithm for Matroid Path-width. SIAM J. Discrete Mathematics (2018?), to appear. URL: arxiv.org/abs/1605.09520. © 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. ?, Dagstuhl (2018), to appear. URL: arxiv.org/abs/1803.01931.
- 2017 (co-authors J. Gajarský, H.R. Tiwary): Parameterized Extension Complexity of Independent Set and Related Problems. Discrete Applied Mathematics (2017), to appear. URL: arxiv.org/abs/1511.08841. DOI 10.1016/j.dam.2017.04.042. © Elsevier B.V.
- 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.
- 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-authors O. Kwon, J. Obdržálek, S. Ordyniak): Tree-depth and Vertex-minors. European J. Combinatorics 56 (2016), 46-56. URL: arxiv.org/abs/1403.7024. DOI 10.1016/j.ejc.2016.03.001. © Elsevier B.V.
- 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.
- 2016 (co-author M. Chimani): Inserting Multiple Edges into a Planar Graph. In: SoCG 2016, LIPIcs Vol. 51, Dagstuhl (2016), 30:1-30:15. URL: arxiv.org/abs/1509.07952. DOI 10.4230/LIPIcs.SoCG.2016.30.
- 2016 (co-authors R. Ganian, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar): Are there any good digraph width measures?. J. of Combinatorial Theory ser. B 116 (2016), 250-286. URL: arxiv.org/abs/1004.1485. DOI 10.1016/j.jctb.2015.09.001. © Elsevier B.V.
- 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.
- 2015 (co-authors R. Ganian, D. Král', J. Obdržálek, J. Schwartz, J. Teska): FO Model Checking of Interval Graphs. Logical Methods in Computer Science 11(4) (2015), paper 11. URL: arxiv.org/abs/1302.6043. DOI 10.2168/LMCS-11(4:11)2015.
- 2015 (co-authors J. Gajarský, J. Obdržálek, S. Ordyniak): Faster Existential FO Model Checking on Posets. Logical Methods in Computer Science 11(4) (2015), paper 8. URL: arxiv.org/abs/1409.4433. DOI 10.2168/LMCS-11(4:8)2015.
- 2015 (co-author G. Salazar): On Hardness of the Joint Crossing Number. In: ISAAC 2015, Lecture Notes in Computer Science 9472, Springer (2015), 603-613. URL: arxiv.org/abs/1509.01787. DOI 10.1007/978-3-662-48971-0_51. © Springer-Verlag.
- 2015 (co-author J. Gajarský): Kernelizing MSO Properties of Trees of Fixed Height, and Some Consequences. Logical Methods in Computer Science 11(1) (2015), paper 19. URL: arxiv.org/abs/1204.5194. DOI 10.2168/LMCS-11(1:19)2015.
- 2015 (co-author M. Derka): Planar Emulators Conjecture Is Nearly True for Cubic Graphs. European J. Combinatorics 48 (2015), 63-70. DOI 10.1016/j.ejc.2015.02.009. © Elsevier B.V. Preprint/file.
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.