Scientific Publications  

This page lists my math and CS publications and conference talks. (I hope all the references and publication information are corect and up to date, but please let me know if you find an error...) If you want to learn more about my scientific (math and cs) research areas, read here; for my academic position read here; and for my academic CV read here.

Please note that the files offered here for download are only preprint versions which are not identical with the published final versions. The final versions of these papers are mostly properties of the mentioned copyright holders, and they can be accessed using the provided DOIs.

Petr Hliněný: Recently published papers

• 2010 (co-author R. Ganian):    On Parse Trees and Myhill-Nerode-type Tools for handling Graphs of Bounded Rank-width.
    Discrete Applied Mathematics 158 (2010), 851-867.
  DOI 10.1016/j.dam.2009.10.018. Copyright © Elsevier B.V. Preprint/file.
• 2010 (co-author R. Ganian):    New results on the complexity of oriented colouring on restricted digraph classes.
    In: SOFSEM 2010, Lecture Notes in Computer Science 5901 (2010), 428-439.
  DOI 10.1007/978-3-642-11266-9_36. Copyright © Springer-Verlag. Preprint/file.
• 2010 (co-author M. Chimani):    Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface.
    In: SODA 2010, SIAM (2010), 918-927.
  URL: www.siam.org/proceedings/soda/2010/soda10.php. Copyright © Society for Industrial and Applied Mathematics. Preprint/file.
• 2009 (co-authors R. Ganian, J. Kneis, A. Langer, J. Obdržálek, P. Rossmanith):    On Digraph Width Measures in Parameterized Algorithmics (extended abstract).
    In: IWPEC 2009, Lecture Notes in Computer Science 5917, Springer (2009), 185-197.
  DOI 10.1007/978-3-642-11269-0_15. Copyright © Springer-Verlag. Preprint/file.
• 2009 (co-author R. Ganian):    Better Polynomial Algorithms on Graphs of Bounded Rank-width.
    In: IWOCA 2009, Lecture Notes in Computer Science 5874, Springer (2009), 266-277.
  DOI 10.1007/978-3-642-10217-2_27. Copyright © Springer-Verlag. Preprint/file.
• 2009 (co-author G. Whittle):    Addendum to Matroid Tree-Width.
    Europ. J. Combin. 30 (2009), 1036-1044.
  DOI 10.1016/j.ejc.2008.09.028. Copyright © Elsevier B.V. Preprint/file.
• 2009 (co-authors M. Chimani, P. Mutzel):    Approximating the Crossing Number of Apex Graphs (Poster).
    In: Graph Drawing 2008, Lecture Notes in Computer Science 5417, Springer Verlag (2009), 432-434.
  DOI 10.1007/978-3-642-00219-9_42. Copyright © Springer-Verlag.
• 2008:    New infinite families of almost-planar crossing-critical graphs.
    Electronic Journal of Combinatorics 15 (2008), #R102.
  URL: www.combinatorics.org/Volume_15/PDF/v15i1r102.pdf.
• 2008 (co-author S. Oum):    Finding Branch-decomposition and Rank-decomposition.
    SIAM J. Computing 38 (2008), 1012-1032.
  DOI 10.1137/070685920. Copyright © Society for Industrial and Applied Mathematics. Preprint/file.
• 2008 (co-authors I. Gitler, J. Leanos, G. Salazar):    The crossing number of a projective graph is quadratic in the face-width.
    Electr. Journal of Combinatorics 15 (2008), www.combinatorics.org, #R46.
  URL: www.combinatorics.org/Volume_15/PDF/v15i1r46.pdf.
• 2008 (co-author G. Salazar):    Stars and Bonds in Crossing-Critical Graphs (Extended abstract).
    In: TGGT 2008 (Paris), Electronic Notes in Discrete Mathematics 31, Elsevier (2008), 271-275.
  DOI 10.1016/j.endm.2008.06.055. Copyright © Elsevier B.V. Preprint/file.
• 2008 (co-authors S. Oum, D. Seese, G. Gottlob):    Width Parameters Beyond Tree-width and Their Applications.
    Invited survey paper, Computer Journal 51 (2008), 326-362.
  DOI 10.1093/comjnl/bxm052. Copyright © Oxford University Press. Preprint/file.
• 2007 (co-author G. Salazar):    Approximating the Crossing Number of Toroidal Graphs.
    In: ISAAC 2007, Lecture Notes in Computer Science 4835, Springer Verlag (2007), 148-159.
  DOI 10.1007/978-3-540-77120-3_15. Copyright © Springer-Verlag. Preprint/file.
• 2007:    Combinatorial Generation of Matroid Representations: Theory and Practice.
    In: Proceedings of the 3rd Asian Applied Computing Conference, Kathmandu, Nepal, December 10-12, 2005, Advances in Computer Science and Engineering: Reports and Monographs - Vol. 2, Imperial College Press, 2007, 3-7.
• 2007 (co-author S. Oum):    Finding branch-decomposition and rank-decomposition (Extended abstract).
    In: ESA 2007, Lecture Notes in Computer Science 4698, Springer Verlag (2007), 163-174.
  DOI 10.1007/978-3-540-75520-3_16. Copyright © Springer-Verlag. Preprint/file.
• 2007 (co-authors I. Gitler, J. Leanos, G. Salazar):    The crossing number of a projective graph is quadratic in the face-width (Extended abstract).
    In: EUROCOMB 2007, Electronic Notes in Discrete Mathematics 29C, Elsevier (2007), 219-223.
  DOI 10.1016/j.endm.2007.07.037. Copyright © Elsevier B.V. Preprint/file.
• 2007:    Some Hard Problems on Matroid Spikes.
    Theory of Computing Systems 41 (2007), 551-562.
  DOI 10.1007/s00224-007-1307-5. Copyright © Springer-Verlag. Preprint/file.
• 2007 (co-author G. Salazar):    On the Crossing Number of Almost Planar Graphs.
    In: Graph Drawing GD 2006, Lecture Notes in Computer Science 4372, Springer Verlag (2007), 162-173.
  DOI dx.doi.org/10.1007/978-3-540-70904-6_17. Copyright © Springer-Verlag. Preprint/file.

All published papers since 1995

Accepted papers (to appear)

• 2010:    20 Years of Negami's Planar Cover Conjecture.
    Graphs and Combinatorics (2010), to appear.
  Preprint/file.
• 2010 (co-author G. Salazar):    Stars and Bonds in Crossing-Critical Graphs.
    Journal of Graph Theory (2010), to appear.
  DOI 10.1002/jgt.20473. Copyright © John Wiley Sons, Inc. Preprint/file.

Some current manuscripts

• 2010 (co-authors R. Ganian, J. Kneis, D. Meister, J. Obdržálek, P. Rossmanith, S. Sikdar):    Are there any good digraph width measures?.
    Submitted (2010), 18 p.
• 2009 (co-authors R. Ganian, J. Obdržálek):    Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width.
    Submitted (2009), 30 p.
  Preprint/file.
• 2009 (co-authors M. Chimani, P. Mutzel):    Vertex Insertion approximates the Crossing Number for Apex Graphs.
    Submitted (2008), 10 p.
  Preprint/file.

Petr Hliněný: Invited talks

• 2008:    20 Years of Negami's Planar Cover Conjecture.
    The 20th Workshop on Topological Graph Theory in Yokohama, Japan. November 24-28, 2008.
  URL: www.ngm.edhs.ynu.ac.jp/negami/tgt/tgt20/index.html. Presentation.
• 2008 ( co-author G. Whittle):    Approaching Tree-Width of Graphs from a Matroidal Perspective.
     ^C-S Grafy 2008, Zadov, Czech Republic. June 9-13, 2008.
  URL: dimatia.fav.zcu.cz/dm/CSGT2008. Presentation.
• 2006 ( co-author D. Seese):    On decidability of MSO theories of combinatorial structures: Towards general matroids?.
    Logic and Combinatorics (organized by Bruno Courcelle), Workshop at CSL'06. September 23-24, 2006.
  URL: www.labri.fr/perso/courcell/WkShopSzeged.html. Presentation.
• 2006:    MACEK - Real Structural Computations with Representable Matroids.
    AXIOM workshop, RISC Institute, Linz, Austria. April 27-29, 2006.
  URL: wiki.axiom-developer.org/WorkshopRisc2006. Presentation.
• 2005 ( co-authors M. Noy, O. Gimenez):    Computing the Tutte Polynomial with Restricted "Width".
    2nd Workshop on Tutte Polynomials and Applications, CRM, UAB Bellaterra, Spain. October 4-7, 2005.
  URL: www.crm.es. Presentation.
• 2005:    O matroidech v teoretické informatice.
    Současné Trendy Teoretické Informatiky, Institute for Theoretical Computer Science. May 13-14, 2005.
• 2004:    Matroid decompositions.
    Workshop on Graph and Hypergraph Decompositions, Wolfgang Pauli Institute Vienna, Austria. December 16-18, 2004.
  URL: www.mat.univie.ac.at/~wpi. Presentation.
• 2004:    Are Matroids Interesting Combinatorial Structures?.
    Workshop on Logic and Graph Transformations, ICGT 2004, Roma, Italy. October 1-2, 2004.
  URL: www.labri.fr/Perso/~courcell/LogicIcgt.html. Presentation.
• 2003 ( co-author G. Whittle):    Matroid Tree-Width.
    Advances in Graph and Matroid Theory, a conference in honour of Neil Robertson's 65th birthday, Columbus USA. December 13-16, 2003.
  URL: www.math.ohio-state.edu/~maharry/Neil65.
• 2003:    Algorithms on Matroids of Bounded Branch-width.
    Fixed Parameter Algorithms, Dagstuhl Seminar #03311, Germany. July 27 - August 1, 2003.
  URL: www.dagstuhl.de.
• 2003:    Branch-width, tree-width, and computational complexity in matroids.
    Současné Trendy Teoretické Informatiky, Institute for Theoretical Computer Science. May 22-23, 2003.
  URL: kam.mff.cuni.cz/conferences/STTI03.
• 2000:    Crossing-Number Critical Graphs have Bounded Pathwidth.
    Workshop on Flows, Cycles and Orientations, PIMS Simon Fraser University, Vancouver Canada. July 3-14, 2000.
• 1999 ( co-author R. Thomas):    On possible counterexamples to Negami's planar cover conjecture.
    Twelfth Cumberland Conference on Combinatorics, Graph Theory and Computing, Louisville, Kentucky USA. May 20-22, 1999.
• 1998:    K4,4 - e has no finite planar cover.
    DIMACS Research and Educational Institute '98, Rutgers University, New Jersey USA. July 27 - August 7, 1998.

Some recent contributed talks

• 2010:    Unified Approach to Polynomial Algorithms on Graphs of Bounded (bi-)Rank-width.
    XIth Conference of Czech Mathematicians CSASC 2010, Prague, CZ. January 25, 2010.
  Presentation.
• 2010:    Approximating the Crossing Number of Graphs Embeddable in Any Orientable Surface.
    ACM-SIAM Symposium on Discrete Algorithms (SODA10), Austin, Texas USA. January 17-20, 2010.
  Presentation.
• 2009:    Planar emulators: On a surprising fall of Fellows conjecture, and beyond.
    Graph Embeddings and Maps on Surfaces GEMS 09, Tále, Slovakia. June 28 - July 3, 2009.
  Presentation.
• 2009:    On Parse Trees and Myhill-Nerode Tools for Graphs of Bounded Rank-width.
    DIMAP workshop on Algorithmic Graph Theory 2009, University of Warwick, UK. March 23-25, 2009.
  Presentation.
• 2009:    21 Years of Negami's Planar Cover Conjecture.
    Workshop on Graph Covers (ATCAGC 2009), Finse, Norway. February 19-21, 2009.
  Presentation.
• 2008:    Graph decompositions, Parse trees, and MSO properties.
    Combinatorial and Computational Aspects of Optimization, Topology and Algebra ACCOTA 2008, Oaxaca, Mexico. December 8-12, 2008.
  URL: www.math.cinvestav.mx/accota. Presentation.
• 2008 ( co-author G. Whittle):    Some Recent Additions to Matroid Tree-Width.
    Netherlands Workshop on Graphs and Matroids, Sittard, NL. July 18-23, 2008.
  Presentation.
• 2007 ( co-author G. Salazar):    Approximating the Crossing Number of Toroidal Graphs.
    18th International Symposium on Algorithms and Computation ISAAC 2007, Sendai, Japan. December 17-19, 2007.
  URL: www.nishizeki.ecei.tohoku.ac.jp/isaac07. Presentation.
• 2007 ( co-author S. Oum):    Finding branch-decomposition and rank-decomposition.
    Joint Meeting of the AMS - NZMS 2007, Wellington, New Zealand. December 12-15, 2007.
  URL: www.mcs.vuw.ac.nz/~mathmeet/amsnzms2007.
• 2007 ( co-author S. Oum):    Finding branch-decomposition and rank-decomposition.
    ALGO: ESA 2007, Eilat, Israel. October 7-11, 2007.
  URL: www.algo07.cs.tau.ac.il/esa.html. Presentation.
• 2007:    Approximating the crossing number for graphs "close to planarity".
    Structure Theory and FPT Algorithmics for Graphs, Digraphs and Hypergraphs, Dagstuhl Seminar #07281, Germany. July 8-13, 2007.
  URL: www.dagstuhl.de. Presentation.
• 2007:    New almost-planar crossing-critical graph families.
    6th Slovenian International Conference on Graph Theory, Bled, Slovenia. June 24-30, 2007.
  URL: conferences.imfm.si/internalPage.py?pageId=8&confId=2. Presentation.
• 2007 ( co-authors I. Gitler, J. Lea~nos, G. Salazar):    The crossing number of a projective graph is quadratic in the face-width.
    Czech-Slovak Conference on Graph Theory 2007, Hradec nad Moravicí, Czech republic. June 11-15, 2007.
  URL: graphs.vsb.cz/grafy2007. Presentation.

All talks since 1995