Assoc. Prof. RNDr. Petr Hliněný, Ph.D.

Basic CV Supervisor Qualifications Publications Projects Teaching

Name, first names, scientific degrees

Hliněný, Petr, born 1971 in Ostrava, CZ, married.

Department/Faculty/University

Faculty of Informatics, Masaryk University

Function, current position

Associate Professor

Education and academic qualifications

2003: Associate Professor of Computer Science, FEI VŠB - TU Ostrava.
2000: Ph.D. in Combinatorics and Discrete Mathematics (advisor Prof. Jan Kratochvíl), Dissertation Contact Representations of Graphs, Faculty of Mathematics and Physics, Charles University, Czech Republic.
1999: PhD. in Algorithms, Combinatorics and Optimization (advisor Prof. Robin Thomas), Dissertation Planar Covers of Graphs: Negami s Conjecture, School of Mathematics, Georgia Institute of Technology, Atlanta, Georgia, USA.
1995: Mgr. (equivalent M.Sc.) in Computer Science, Faculty of Mathematics and Physics, Charles University, Czech Republic.

Professional experience

2005- : Faculty of Informatics, Masaryk University, Brno, Czech Republic.
2003-2007 : Department of Computer Science, Technical University Ostrava, Czech Republic.
2002-2003: Institute of Mathematics and Computer Science, Matej Bel University, Slovakia.
2000-2004: Institute of Theoretical Computer Science, Charles University.
2000-2002: School of Mathematical and Computing Sciences, Victoria University, New Zealand.
1999-2000: The Fields Institute, University of Toronto, Canada; J.E. Marsden Distinguished Postdoctoral Fellow.

Teaching activities

Courses:
2010: Úvod do informatiky, Graph Theory, Advanced Graph Theory.
2009: Úvod do informatiky, Graph Theory, Advanced Graph Theory, Optimization.
2008: Úvod do informatiky, Teorie Grafů, Advanced Graph Theory, Advanced Matroid Theory.
2007: Úvod do informatiky, Teorie Grafů, Advanced Graph Theory, Optimization; FI MU Brno.
2006: Úvod do informatiky 2x, Teorie Grafů, Matematická logika, Advanced Graph Theory; FI MU Brno.
2005: Optimalizační úlohy; FI MU Brno.
2004,2005: Úvod do teoretické informatiky; FEI VŠB - TU Ostrava.
2004: Optimalizační úlohy; FEI VŠB - TU Ostrava.
2003,2004: Diskrétní matematika; FEI VŠB - TU Ostrava.
2003: Algebra, Teorie Grafů; UMB Banská Bystrica.
2002: Teorie čísel, Pravděpodobnostní algoritmy, UMB Banská Bystrica.
1999: Introduction to Programming; CS University of Toronto, Canada.
1998: Applied Combinatorics; Mathematics, Georgia Tech, USA.
1996,1997: Algebraické metody v kombinatorice; KAM MFF UK Praha.
Ph.D. students (in progress):
2008- : RNDr. Robert Ganian (FI MU Brno).
2010- : Mgr. Ondrej Moriš (FI MU Brno).
Bc. and Msc. students:
current: Martin Derka, Matěj Klusáček, Jakub Gajarský (FI MU), Jozef Janovský, Marek Derňár (PřF MU).
2010: Ondrej Moriš, Pavel Zářecký, Martin Derka.
2009: Pavel Jurkas.
2008: Stanislav Bršlica, Tibor Zsitva, Martin Juránek, Robert Ganian, Ondrej Moriš (FI MU Brno).
2007: Petr Výmola (FI MU Brno), Vít Michalec (FEI VŠB - TUO).
2006: Jakub Mareček (FI MU Brno).
2005: Nikola Ciprich, Ondřej Jeseňák, Marian Krucina, Petr Vašíček (FEI VŠB - TUO).

Research activities

Discrete mathematics: graph and matroid structural theories, combinatorial algorithms, "width" parameters, topological graph theory and crossing numbers.
Theoretical computer science: complexity and parametrized complexity of (the aforementioned) combinatorial problems.
Applications: route planning in GPS navigation.
Projects, grants:
2009-2010: Holder of Structural Graph Theory and Parameterized Complexity, GAČR 201/09/J021 billateral with RWTH Aachen.
2008-2010: Holder of Utilization of Structural and Width Parameters in Combinatorics and Algorithmic Complexity, GAČR 201/08/0308.
2005-2009: Participation in the Institute for Theoretical Computer Science, project 1M0545.
2005-2007: Holder of Structural properties and algorithmic complexity of discrete problems, GAČR 201/05/0050.
2005: Holder of FRVŠ 2270/2005: Výuka optimalizačních úloh.
2000-2004: Participated in the Institute for Theoretical Computer Science, project LN00A056.
2000-2002: Participated in the NZ Marsden Fund grant, Matroid Structure Theory, Geoff Whittle.
1999-2000: J.E. Marsden Distinguished Postdoctoral Fellow, The Fields Institute.

Professional stays abroad

... see employment... plus
2006: BIRS Banff, Canada, 1 week.
2004: UA San Luis Potosi, Mexico, 1 week.
2004: UPC Barcelona, 1 month (COMBSTRU network).
1999: PIMS Vancouver, Canada, 1 month.
1995: University of Oregon, USA, 2 months (Fulbright grant).

Non-university activities

Membership AMS, EATCS, MVS JČMF.
Managing editor Acta Univ. Matthiae Belii - Mathematics.

Most significant professional accomplishments

2010: J. Combin. Theory ser. B Top cited article 2005-2010 award.
1999/2000: Jerrold E. Marsden Distinguished Postdoctoral Fellowship at The Fields Institute, Toronto, Canada.
1995: Bolzano prize in Computer Science for the work Contact Graphs of Curves (an extended version of thesis) at the Faculty of Mathematics and Physics, Charles University.

Refereed publications

HLINĚNÝ, Petr a Markus CHIMANI a Petra MUTZEL. Vertex insertion approximates the crossing number of apex graphs. European Journal of Combinatorics, Elsevier, 33, 3, od s. 326-335, 10 s. ISSN 0195-6698. 2012. doi:10.1015/j.ejc.2011.09.009. info
HLINĚNÝ, Petr a Ondrej MORIŠ. Scope-Based Route Planning. In ESA’11: Proceedings of the 19th conference on Annual European Symposium. Berlin Heidelberg: LNCS 6942, Springer-Verlag, 2011. od s. 445-456, 12 s. ISBN 978-3-642-23718-8. preprint info
GANIAN, Robert a Petr HLINĚNÝ a Jan OBDRŽÁLEK. Clique-width: When Hard Does Not Mean Impossible. In Thomas Schwentick and Christoph D{\"u}rr. 28th International Symposium on Theoretical Aspects of Computer Science STACS2011. 2011. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2011. od s. 404-415, 12 s. ISBN 978-3-939897-25-5. STACS2011DOI info
CHIMANI, Markus a Petr HLINĚNÝ. A Tighter Insertion-based Approximation of the Crossing Number. In Luca Aceto, Monika Henzinger and Jirí Sgall. Automata, Languages and Programming 38th International Colloquium, ICALP 2011. Gremany: Springer, 2011. od s. 122-134, 13 s. ISBN 978-3-642-22005-0. doi:10.1007/978-3-642-22006-7_11. DOI info
HLINĚNÝ, Petr a Eva JELÍNKOVÁ a Jan KRATOCHVÍL a Ondřej SUCHÝ. Parameterized Problems Related to Seidel's Switching. Discrete Mathematics & Theoretical Computer Science, France: DMTCS, 13, 2, od s. 19-42, 24 s. ISSN 1365-8050. 2011. paper info
HLINĚNÝ, Petr a Ondrej MORIŠ. Generalized Maneuvers in Route Planning. In MEMICS 2011 Proceedings LNCS. Berlin Heidelberg: Springer-Verlag, 2011. to appear. info
HLINĚNÝ, Petr a Martin DERKA a Markus CHIMANI a Matěj KLUSÁČEK. How Not to Characterize Planar-emulable Graphs. In Costas S. Iliopoulos and William F. Smyth. IWOCA 2011, Lecture Notes in Computer Science 7056. Německo: Springer Verlag, 2011. od s. 106-120, 15 s. ISBN 978-3-642-25010-1. doi:10.1007/978-3-642-25011-8_9. info
HLINĚNÝ, Petr a Markus CHIMANI. Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface. In ACM-SIAM Symposium on Discrete Algorithms (SODA 2010). USA, internet: SIAM / ACM, 2010. od s. 918-927, 10 s. ISBN 978-0-89871-698-6. Proceedings addressconference info
GANIAN, Robert a Petr HLINĚNÝ. On parse trees and Myhill-Nerode-type tools for handling graphs of bounded rank-width. Discrete Applied Mathematics, Amsterdam: Elsevier B.V., 158, 1, od s. 851-867, 17 s. ISSN 0166-218X. 2010. DOI info
GANIAN, Robert a Petr HLINĚNÝ. New results on the complexity of oriented colouring on restricted digraph classes. In SOFSEM 2010, Lecture Notes in Computer Science 5901. 5901. vyd. Berlin: Springer, 2010. od s. 428-439, 12 s. ISBN 978-3-642-11265-2. DOI info
HLINĚNÝ, Petr a Antonín KUČERA. 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010). 2010. info
GANIAN, Robert a Petr HLINĚNÝ a Jan OBDRŽÁLEK a Joachim KNEIS a Daniel MEISTER a Somnath SIKDAR a Peter ROSSMANITH. Are there any good digraph width measures? In Parameterized and exact computation, IPEC 2010. 6478. vyd. India: Lecture Notes in Computer Science, Springer-Verlag, 2010. od s. 135-146, 12 s. ISBN 978-3-642-17492-6. DOI info
GANIAN, Robert a Petr HLINĚNÝ a Jan OBDRŽÁLEK. Better algorithms for satisfiability problems for formulas of bounded rank-width. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). 2010. vyd. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS, 2010. od s. 73-83, 11 s. ISBN 978-3-939897-23-1. URL DOI info
HLINĚNÝ, Petr a Gelasio SALAZAR. Stars and Bonds in Crossing-Critical Graphs. Journal of Graph Theory, New York: John Wiley & Sons, 65, 3, od s. 198-215, 18 s. ISSN 0364-9024. 2010. DOI info
HLINĚNÝ, Petr a Markus CHIMANI a Petra MUTZEL. Approximating the Crossing Number of Apex Graphs (poster). In Symposium Graph Drawing 2008, Lecture Notes in Computer Science. 5417. vyd. Berlin: Springer Verlag, 2009. od s. 432-434, 3 s. ISBN 978-3-642-00218-2. conference info
HLINĚNÝ, Petr a Geoff WHITTLE. Addendum to Matroid Tree-Width. European Journal of Combinatorics, Elsevier, 30, 4s. 1036-1044. ISSN 0195-6698. 2009. doi info
GANIAN, Robert a Petr HLINĚNÝ. Better Polynomial Algorithms on Graphs of Bounded Rank-width. In IWOCA 2009: International Workshop On Combinatorial Algorithms, Lecture Notes in Computer Science 5874. 5874. vyd. Berlin: Springer, 2009. od s. 266-277, 12 s. ISBN 978-3-642-10216-5. DOI info
GANIAN, Robert a Petr HLINĚNÝ a Jan OBDRŽÁLEK a Alexander LANGER a Joachim KNEIS a Peter ROSSMANITH. On Digraph Width Measures in Parameterized Algorithmics. In IWPEC 2009: International Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science. 5917. vyd. Berlin: Springer Verlag, 2009. od s. 185-197, 13 s. ISBN 978-3-642-11268-3. ConferenceDOI info
HLINĚNÝ, Petr a Gelasio SALAZAR a Isidoro GITLER a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width. Electronic Journal of Combinatorics, internet: -, 15, 1, od s. R46, 8 s. ISSN 1077-8926. 2008. online paper info
HLINĚNÝ, Petr. Approaching tree-width of graphs from matroidal perspective. In 43. česko-slovenská konference Grafy 2008. 2008. conference info
HLINĚNÝ, Petr a Gelasio SALAZAR. Stars and Bonds in Crossing-Critical Graphs. Electronic Notes in Discrete Mathematics, Elsevier, 31, 1, od s. 271-275, 5 s. ISSN 1571-0653. 2008. ISSN 1571-0653. conferenceDOI info
HLINĚNÝ, Petr a Sang-il OUM. Finding branch-decomposition and rank-decomposition. SIAM Journal on Computing, USA: SIAM, 38, 3, od s. 1012-1032, 21 s. ISSN 0097-5397. 2008. doi info
HLINĚNÝ, Petr a Robert GANIAN. Automata Approach to Graphs of Bounded Rank-width. In Mirka Miller and Koichi Wada. International Workshop on Combinatorial Algorithms IWOCA 2008. United Kingdom: Proceedings of the International Workshop on Combinatorial Algorithms 2008, College Publications, 2008. od s. 4-15, 12 s. ISBN 978-1-904987-74-1. conference info
HLINĚNÝ, Petr. New infinite families of almost-planar crossing-critical graphs. Electronic Journal of Combinatorics, internet: -, 15, 1, od s. R102, 12 s. ISSN 1077-8926. 2008. online paper info
HLINĚNÝ, Petr. 20 years of Negami's planar cover conjecture. In The 20th Workshop on Topological Graph Theory in Yokohama (TGT20), Japan. 2008. DOI info
HLINĚNÝ, Petr. Some Hard Problems on Matroid Spikes. Theory of Computing Systems, New York: Springer, 41, 1, od s. 551-562, 12 s. ISSN 1432-4350. 2007. doi info
HLINĚNÝ, Petr a Gelasio SALAZAR. On the Crossing Number of Almost Planar Graphs. In Graph Drawing, Symposium GD2006. 4372. vyd. Berlin: Springer Verlag, 2007. od s. 162-173, 12 s. ISBN 3-540-70903-7. conference info
HLINĚNÝ, Petr a Georg GOTTLOB a Detlef SEESE a Sang-il OUM. Width Parameters Beyond Tree-width and Their Applications. Computer Journal, UK: Oxford University Press, 51, 3, od s. 326-362, 37 s. ISSN 0010-4620. 2007. doi info
HLINĚNÝ, Petr a Gelasio SALAZAR. Approximating the Crossing Number of Toroidal Graphs. In International Symposium on Algorithms and Computation (ISAAC 2007). Berlin: Springer Verlag, 2007. s. 148-159. ISBN 978-3-540-77118-0. conferencedoi info
HLINĚNÝ, Petr a Gelasio SALAZAR a Isidoro GITLER a Jesus LEANOS. The crossing number of a projective graph is quadratic in the face--width (Extended abstract). Electronic Notes in Discrete Mathematics, Elsevier, 29, C, od s. 219-223, 5 s. ISSN 1571-0653. 2007. conferencedoi info
HLINĚNÝ, Petr a Sang-il OUM. Finding branch-decomposition and rank-decomposition (Extended abstract). In European Symposium on Algorithms (ESA 2007). Berlin: Springer Verlag, 2007. s. 163-174. ISBN 978-3-540-75519-7. conferencedoi info
HLINĚNÝ, Petr. The Tutte Polynomial for Matroids of Bounded Branch-Width. Combin. Prob. Computing, UK: Cambridge Univ. Press, 15, 3s. 397-409. ISSN 0963-5483. 2006. doiURL info
HLINĚNÝ, Petr. Crossing Number is Hard for Cubic Graphs. Journal of Combinatorial Theory, Ser B, Amsterdam: Elsevier B.V., 96, 4, od s. 455-471, 17 s. ISSN 0095-8956. 2006. URL info
HLINĚNÝ, Petr. Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids. Journal of Combinatorial Theory, Ser B, Amsterdam: Elsevier B.V., 96, 3, od s. 325-351, 27 s. ISSN 0095-8956. 2006. URL info
HLINĚNÝ, Petr a Detlef SEESE. Trees, grids, and MSO decidability: From graphs to matroids. Theoretical Computer Science, Amsterdam: Elsevier, 351, 3, od s. 372-393, 22 s. ISSN 0304-3975. 2006. URL info
HLINĚNÝ, Petr. Equivalence-free exhaustive generation of matroid representations. Discrete Applied Mathematics, Amsterdam: Elsevier B.V., 154, 8, od s. 1210-1222, 13 s. ISSN 0166-218X. 2006. URL info
HLINĚNÝ, Petr. Combinatorial Generation of Matroid Representations: Theory and Practice. Acta Universitatis Matthiae Belii, Series Mathematics, Banska Bystrica, Slovakia: Matej Bel University, 12, 1s. 31-41. 2006. URL info
GIMENEZ, Omer a Petr HLINĚNÝ a Marc NOY. Computing the Tutte Polynomial on Graphs of Bounded Clique-Width. SIAM Journal on Discrete Mathematics, Philadelphia: SIAM, 20, 4, od s. 932-946, 15 s. ISSN 0895-4801. 2006. doi info
HLINĚNÝ, Petr a Geoff WHITTLE. Matroid Tree-Width. European Journal of Combinatorics, Elsevier, 27, 7s. 1117-1128. ISSN 0195-6698. 2006. doi info
HLINĚNÝ, Petr a Winfried HOCHSTATTLER a Luis GODDYN. Balanced Signings and the Chromatic Number of Oriented Matroids. Combin. Prob. Computing, UK: Cambridge Univ. Press, 15, 4s. 523-539. ISSN 0963-5483. 2006. doi info
HLINĚNÝ, Petr. On Matroid Representability and Minor Problems. In 31st International Symposium, MFCS 2006. 4162. vyd. Berlin: Springer Verlag, 2006. od s. 505-516, 12 s. ISBN 3-540-37791-3. URL info
HLINĚNÝ, Petr a Jim GEELEN a Geoff WHITTLE. Bridging Separations in Matroids. SIAM Journal on Discrete Mathematics, Philadelphia: SIAM, 18, 3s. 638-646. ISSN 0895-4801. 2005. info
HLINĚNÝ, Petr. MACEK: A software package for real structural computations with representable matroids. verze 1.2. 2005. Current home page of MACEK, with an online trial interface. info
GIMENEZ, Omer a Petr HLINĚNÝ a Marc NOY. Computing the Tutte Polynomial on Graphs of Bounded Clique-Width (extended abstract). D. Kratsch (Ed.). In WG 2005. Berlin: Springer Verlag, 2005. od s. 59-68, 10 s. ISBN 978-3-540-31000-6. conferencedoi info
HLINĚNÝ, Petr. A Parametrized Algorithm for Matroid Branch-Width. SIAM Journal on Computing, USA: SIAM, 35, 2, od s. 259 - 277, 19 s. ISSN 0097-5397. 2005. URL info
HLINĚNÝ, Petr a Robin THOMAS. On possible counterexamples to Negami's planar cover conjecture. Journal of Graph Theory, New York: John Wiley & Sons, 46, 3, od s. 183-206, 24 s. ISSN 0364-9024. 2004. URL info
HLINĚNÝ, Petr. Crossing Number is Hard for Cubic Graphs (extended abstract). Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 3153s. 772-781. ISSN 0302-9743. 2004. info
HLINĚNÝ, Petr a Detlef SEESE. On Decidability of MSO Theories of Representable Matroids. Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 3162s. 96-107. ISSN 0302-9743. 2004. info
HLINĚNÝ, Petr. Using a Computer in Matroid Theory Research. Acta Math. Univ. M. Belii, Slovensko: UMB BB, 11, 1s. 27-44. 2004. URL info
HLINĚNÝ, Petr. On Matroid Properties Definable in the MSO Logic. Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 2747s. 470-479. ISSN 0302-9743. 2003. info
HLINĚNÝ, Petr. Branch-Width, Parse Trees, and Monadic Second-Order Logic for Matroids (Extended Abstract). Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 2607s. 319-330. ISSN 0302-9743. 2003. info
HLINĚNÝ, Petr. Crossing-Number Critical Graphs have Bounded Pathwidth. Journal of Combinatorial Theory, Ser B, .: Elsevier B.V., 88, 3s. 347-367. ISSN 0095-8956. 2003. info
HLINĚNÝ, Petr. A new proof for chordal graphs. Acta Math. Univ. M. Belii, Slovensko: UMB BB, 10, 1s. 17-19. 2003. URL info
HLINĚNÝ, Petr. Crossing-Critical Graphs and Path-Width. Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 2265, 2265s. 102-113. ISSN 0302-9743. 2002. info
HLINĚNÝ, Petr. On the Excluded Minors for Matroids of Branch-Width Three. Electronic Journal of Combinatorics, internet: -, 9, R32s. 0-11. ISSN 1077-8926. 2002. URL info
HLINĚNÝ, Petr. Another two graphs with no planar covers. Journal of Graph Theory, New York: John Wiley & Sons, 37, 4s. 227-242. ISSN 0364-9024. 2001. URL info
HLINĚNÝ, Petr a Jan KRATOCHVÍL. Representing graphs by disks and balls (a survey of recognition complexity results). Discrete Mathematics, .: Elsevier B.V., 229, 1s. 101-124. ISSN 0166-218X. 2001. info
HLINĚNÝ, Petr. An Addition to Art Galleries with Interior Walls. Discrete and Computational Geometry, .: Springer, 25, 3s. 311-314. ISSN 0179-5376. 2001. info
HLINĚNÝ, Petr. Contact graphs of line segments are NP-complete. Discrete Mathematics, .: Elsevier B.V., 235, 1s. 95-106. ISSN 0166-218X. 2001. info
HLINĚNÝ, Petr. A note on possible extensions of Negami's conjecture. Journal of Graph Theory, New York: John Wiley & Sons, 32, 3s. 234-240. ISSN 0364-9024. 1999. URL info
HLINĚNÝ, Petr. K4,4-e has no finite planar cover. Journal of Graph Theory, New York: John Wiley & Sons, 27, 1s. 51-60. ISSN 0364-9024. 1998. URL info
HLINĚNÝ, Petr. The maximal clique and colourability of curve contact graphs. Discrete Applied Mathematics, .: Elsevier B.V., 81, 1s. 59-68. ISSN 0166-218X. 1998. info
HLINĚNÝ, Petr. Classes and recognition of curve contact graphs. Journal of Combinatorial Theory, Ser B, .: Elsevier B.V., 74, 1s. 87-103. ISSN 0095-8956. 1998. info
HLINĚNÝ, Petr a Jan KRATOCHVIL. Computational complexity of the Krausz dimension of graphs. Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 1335s. 214-228. ISSN 0302-9743. 1997. info
HLINĚNÝ, Petr. Touching graphs of unit balls. Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 1353s. 350-358. ISSN 0302-9743. 1997. info
HLINĚNÝ, Petr. Contact graphs of curves (extended abstract). Lecture Notes in Computer Science, Berlin, Heidelberg: Springer-Verlag, 1027s. 312-323. ISSN 0302-9743. 1996. info
HLINĚNÝ, Petr a Aleš KUBĚNA. A note on intersection dimensions of graph classes. Comment. Math. Univ. Carolinae, Praha: MFF UK, 36, 1s. 255-260. ISSN 0010-2628. 1995. info

Last update: 2011/03/07

top