My teaching and Information for students
Prof. RNDr. Petr Hliněný, Ph.D.
Teaching: Autumn, IB000 and MA010
- FI:IB000 Mathematical Foundations of CS;
- FI:MA010 Graph Theory;
Teaching: Spring selective seminars
FI:IV125 Formela lab seminar;
- up-to-date seminar details.
- My research seminar topics are related to advanced structural or topological graph theory (replacing previous separate subjects MA051,2,3).
- And, the following IV119 seminar for young students...
FI:IV119 Seminar on Discrete Mathematical Methods
This is an informal Spring seminar for all students who like mathematics, and especially beatiful mathematical problems, solutions, and proofs - as presented to us by famous "Proofs from THE BOOK". If you have ever tried "Mathematical olympiad" or other math competitions at elementary and high schools, then drop by and see how easy is to get from math fun to serious real science. Especially first year students with interest in math are most warmly welcome!
- For all young students who like nice clean mathematics, no prerequisites required.
Official seminar entry in IS
- Spring 2018 seminar: in C417, Tuesday 10-12 every week
- So, which problems to deal with this year? We will (traditionally) begin with the number of primes, and we will also look this year at various proofs of Euler's formula... (see this) Then we will pick other nice problems (and their solutions) from number theory, discrete geometry, combinatorics and graphs...
- Come and see us (even if you participated in 2017 - we will study different topics of The Book)...
- See also a list of past 2017 topics here.
Bc/Ms thesis topics at FI MU Brno, CZ
Generally, any chosen sufficiently interesting topic of graph theory or related algorithmic questions, including parameterized complexity, 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:
- FO properties of geometric graphs, Obstructions for graphs of low rank-depth, Characterizing DAG-depth of directed graphs, 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 our group.
Read about Ph.D. study in our group
Recent achievements of our students (2012)
- 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 prize R. Ganian (2008),
2nd prizes O. Moriš (2008), M. Derka (2010), M. Klusáček (2011), J. Gajarský (2012), M. Bezek (2016).
- Student research grants at MU:
R. Ganian in 2009-11, M. Derka in 2010-11.
- Best student papers of:
SOFSEM 2011 (R. Ganian), MEMICS 2011 (O. Moriš).
- Selected publication coauthored with my students:
- 2018 (co-authors O. Cagirici, B. Roy): On Colourability of Polygon Visibility Graphs. In: FSTTCS 2017, LIPIcs Vol. 93, Dagstuhl (2018), 21:1--21:14. DOI 10.4230/LIPIcs.FSTTCS.2017.21.
- 2018 (co-authors F. Pokrývka, B. Roy): FO model checking of geometric graphs. In: IPEC 2017, LIPIcs Vol. 89, Dagstuhl (2018), 19:1--19:12. URL: arxiv.org/abs/1709.03701. DOI 10.4230/LIPIcs.IPEC.2017.19.
- 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-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 M.Bračič, D. Bokal, M. Derňár): On Degree Properties of Crossing-critical Families of Graphs. In: Graph Drawing 2015, Lecture Notes in Computer Science 9411, Springer (2015), 75--86. DOI 10.1007/978-3-319-27261-0_7. © Springer-Verlag. Preprint/file.
- 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-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.
- 2014 (co-authors R. Ganian, A. Langer, J. Obdržálek, P. Rossmanith, S. Sikdar): Lower Bounds on the Complexity of MSO1 Model-Checking. Journal of Computer and System Sciences 80 (2014), 180--194. URL: arxiv.org/abs/1109.5804. DOI 10.1016/j.jcss.2013.07.005. © Elsevier B.V.
- 2013 (co-authors M. Chimani, M. Derka, M. Klusáček): How Not to Characterize Planar-emulable Graphs. Advances in Applied Mathematics 50 (2013), 46--68. URL: arxiv.org/abs/1107.0176. DOI 10.1016/j.aam.2012.06.004. © Elsevier B.V. Addendum.
- 2011 (co-author O. Moriš): Scope-based route planning. In: ESA 2011, Lecture Notes in Computer Science 6942, Springer (2011), 445--456. URL: arxiv.org/abs/1101.3182. DOI 10.1007/978-3-642-23719-5_38. © Springer-Verlag.