Michal Kotrbčík

E-mail:

kotrbcik at dcs dot fmph dot uniba dot sk (semi-permanent)

Postdoctoral fellow
School of Mathematics and Physics
The University of Queensland

St. Lucia
Brisbane 4072
Australia

Currently I am postdoc in the group of Darryn Bryant and Barbara Maenhaut at The University of Queensland, working on combinatorial configurations and graph decompositions.

Previously, I was postdoc in the online algorithms group of Joan Boyar and Kim Skak Larsen, and in the group of Petr Hlinený. I did my Ph.D. in topological graph theory with Martin Škoviera.

Research interests:

• Graph theory and graph algorithms - both theory and implementations.

Areas:

Topological Graph Theory • Matchings • Online Algorithms • Algorithm Engineering • Experimental Algorithms


Papers:

• Linear Time Canonicalization and Enumeration of Non-Isomorphic 1-Face Embeddings
  With M. Hellmuth, A. S. Knudsen, D. Merkle, and N. Nøjgaard.
  Submitted.


• Relaxing the Irrevocability Requirement for Online Graph Algorithms [arXiv full version]
  With J. Boyar, L. M. Favrholdt, and K. S. Larsen.
  (WADS'17) To appear in Proceedings of 15th Algorithms and Data Structures Symposium WADS'17.


• Online Dominating Set [Open access] [arXiv full version] [BibTeX]
  With J. Boyar, S. J. Eidenbenz, L. M. Favrholdt, and K. S. Larsen.
  (SWAT'16) Proceedings of 15th Scandinavian Symposium and Workshops on Algorithm Theory SWAT'16,
  R. Pagh, ed., pp. 21:1 - 21:15, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2016.


• A Practical Method for the Minimum Genus of a Graph: Models and Experiments
  [Publisher's version]
  With S. Beyer, M. Chimani, and I. Hedtke.
  (SEA'16) Proceedings of 15th International Symposium on Experimental Algorithms SEA'16,
  V. A. Goldberg and K. S. Alexander, eds., pp. 75 - 88, Springer International Publishing, 2016.


• Editing to a dense and a sparse graph class. [Publisher's version]
  With R. Královič and S. Ordyniak.
  (LATIN'16) Proceedings of 12th. Latin American Theoretical Informatics Symposium LATIN'16,
  E. Kranakis, G. Navarro, and Ch. Edgar, eds., pp. 562 - 575, Springer Berlin Heidelberg, 2016.


• Grunbaum colorings of even triangulations on surfaces [Manuscript]
  With N. Matsumoto, B. Mohar, A. Nakamoto, K. Noguchi, K. Ozeki, and A. Vodopivec.
  Submitted.


• Equimatchable factor-critical graphs and independence number 2. [arXiv]
  With E. Eiben.
  Manuscript.


• Simple greedy 2-approximation algorithm for the maximum genus of a graph [arXiv]
  With M. Škoviera.
  Manuscript.


• Locally-maximal embeddings of graphs on surfaces. [Publisher's version]
  With M. Škoviera.
  (EuroComb'13) The Seventh European Conference on Combinatorics, Graph Theory and Applications,
  J. Nešetřil and M. Pellegrini, eds., CRM Series, Scuola Normale Superiore, pp. 215-220, 2013. (Proceedings of EuroComb 2013.)


• Equimatchable graphs on surfaces. [Publisher's version] [arXiv]
  With E. Eiben.
  (JGT) J. Graph Theory 81 (1): 35-49, 2016.


• Genus of the cartesian product of triangles. [Open access]
  With T. Pisanski.
  (E-JC) Electronic J. Combinatorics 22 (4), #P4.2, 2015.
  Supplementary material [Open access at publisher's page]


• Maximum genus, connectivity, and Nebeský's theorem. [Open access]
  With D. Archdeacon, R. Nedela, and M. Škoviera.
  (AMC) Ars Mathematica Contemporanea 9 (1): 51-61, 2015.


• Genus distribution of 3-regular series-parallel graphs. [Open access] [arXiv]
  With J. L. Gross and T. Sun.
  (DMTCS) Discrete Mathematics & Theoretical Computer Science 16 (3): 129-146, 2014.


• Matchings, cycle bases, and the maximum genus of a graph (E-JC). [Open access]
  With M. Škoviera.
  (E-JC) Electronic J. Combinatorics 19 (3), #P3, 2012.


• A note on disjoint cycles (IPL). [Publisher's version]
  (IPL) Information Processing Letters 112 (4): 135-137, 2012.


• Maximum genus of regular graphs (EuroComb'11). [Publisher's version]
  (EuroComb'11) Electronic notes in Discrete Mathematics 38 (1): 535-540, 2011. (Proceedings of EuroComb 2011.)

Last updated: 8th of May 2017.