Theoretical Computer Science flagPL flagEN
Faculty of Mathematics and Computer Science
Jagiellonian University
 
    informatyka analityczna  
UJ coat of arms
Foundations of Computer Science
 
 

Bartosz Walczak

PhD

phone: (+48) 12 664 75 92
fax: (+48) 12 664 66 72
email: email
office: ul. Łojasiewicza 6, 30-348 Kraków
room: 3067
 
 
curriculum vitae:en: [pdf]
msc thesis:[pdf]
phd thesis:[pdf]
photo

research interests
Graph and poset theory
Algorithms
Discrete and computational geometry
Extremal combinatorics
Combinatorial games

selected publications
  • Kolja Knauer, Bartosz Walczak, Graph drawings with one bend and few slopes, submitted [arXiv]
  • William T. Trotter, Bartosz Walczak, Ruidong Wang, Dimension and cut vertices: an application of Ramsey theory, submitted [arXiv]
  • Tomasz Krawczyk, Bartosz Walczak, Asymmetric coloring games on incomparability graphs, EuroComb 2015, to appear in Electronic Notes in Discrete Mathematics [arXiv]
  • Martin Balko, Vít Jelínek, Pavel Valtr, Bartosz Walczak, in: 31st International Symposium on Computational Geometry (SoCG 2015), Leibniz International Proceedings in Informatics (LIPIcs) 34 (2015), 406-420 [DOI, arXiv]
  • Adam Gągol, Piotr Micek, Bartosz Walczak, Graph sharing game and the structure of weighted graphs with a forbidden subdivision, submitted [arXiv]
  • Bartosz Walczak, Minors and dimension, in: 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), SIAM (2015), 1698-1707 [DOI, arXiv]
  • Bartosz Walczak, Triangle-free geometric intersection graphs with no large independent sets, Discrete and Computational Geometry 53 (2015), 221-225 [DOI, arXiv]
  • Tomasz Krawczyk, Bartosz Walczak, On-line approach to off-line coloring problems on graphs with geometric representations, submitted [arXiv]
    Preliminary version: Coloring relatives of interval overlap graphs via on-line games, in: Automata, Languages, and Programming (ICALP 2014, part I), Lecture Notes in Computer Science 8572 (2014), 738-750 [DOI]
  • János Pach, Bartosz Walczak, Decomposition of multiple packings with subquadratic union complexity, to appear in Combinatorics, Probability and Computing [arXiv]
  • Alexandre Rok, Bartosz Walczak, Outerstring graphs are χ-bounded, in: 30th Annual Symposium on Computational Geometry (SoCG 2014), ACM (2014), 136-143 [DOI, arXiv]
  • Michał Lasoń, Piotr Micek, Arkadiusz Pawlik, Bartosz Walczak, Coloring intersection graphs of arc-connected sets in the plane, Discrete and Computational Geometry 52 (2014), 399-415 [DOI, arXiv]
  • Andrew Suk, Bartosz Walczak, New bounds on the maximum number of edges in k-quasi-planar graphs, Computational Geometry: Theory and Applications, in press [DOI, arXiv]
    Preliminary version in: Graph Drawing (GD 2013), Lecture Notes in Computer Science 8242 (2013), 95-106 [DOI]
  • Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, Ruidong Wang, Tree-width and dimension, Combinatorica, in press [DOI, arXiv]
  • Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak, Coloring triangle-free rectangle overlap graphs with O(log log n) colors, Discrete and Computational Geometry 53 (2015), 199-220 [DOI, arXiv]
    Preliminary version: Coloring triangle-free rectangular frame intersection graphs with O(log log n) colors, in: Graph-Theoretic Concepts in Computer Science (WG 2013), Lecture Notes in Computer Science 8165 (2013), 333-344 [DOI]
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak, Triangle-free geometric intersection graphs with large chromatic number, Discrete and Computational Geometry 50 (2013), 714-726 [DOI, arXiv]
  • Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk, Michał Lasoń, Piotr Micek, William T. Trotter, Bartosz Walczak, Triangle-free intersection graphs of line segments with large chromatic number, Journal of Combinatorial Theory, Series B 105 (2014), 6-10 [DOI, arXiv]
  • Kolja Knauer, Piotr Micek, Bartosz Walczak, Outerplanar graph drawings with few slopes, Computational Geometry: Theory and Applications 47 (2014), 614-624 [DOI, arXiv]
    Preliminary version in: Computing and Combinatorics (COCOON 2012), Lecture Notes in Computer Science 7434 (2012), 323-334 [DOI]
  • Michał Lasoń, Piotr Micek, Noah Streib, William T. Trotter, Bartosz Walczak, An extremal problem on crossing vectors, Journal of Combinatorial Theory, Series A 128 (2014), 41-55 [DOI, arXiv]
  • Pavel Klavík, Jan Kratochvíl, Tomasz Krawczyk, Bartosz Walczak, Extending partial representations of function graphs and permutation graphs, in: Algorithms – ESA 2012, Lecture Notes in Computer Science 7501 (2012), 671-682 [DOI, arXiv]
  • Piotr Micek, Bartosz Walczak, Parity in graph sharing games, Discrete Mathematics 312 (2012), 1788-1795 [DOI]
  • Piotr Micek, Bartosz Walczak, A graph-grabbing game, Combinatorics, Probability and Computing 20 (2011), 623-629 [DOI]
  • Bartosz Walczak, A simple representation of subwords of the Fibonacci word, Information Processing Letters 110 (2010), 956-960 [DOI]

  • some recent collaborators 
    Kolja KnauerAix-Marseille Université
    Jan KratochvílCharles University
    Tomasz KrawczykJagiellonian University
    János PachÉcole Polytechnique Fédérale de Lausanne
    Ignaz RutterKarlsruher Institut für Technologie
    William T. TrotterGeorgia Institute of Technology
    Pavel ValtrCharles University

    grants
    2010 - 2012 Movement tracking in monitored zones
      Ministry of Science and Higher Education
      R00 0081 11
    2010 - 2012 Efficient video image sharpening in a distributed environment
      Małopolskie Centre of Entrepreneurship
      MCP.ZS.4110-123.1/2009
    2010 - 2012 On-line algorithms and combinatorial games
      Ministry of Science and Higher Education
      N206 4923 38
    2011 - 2014 Graph drawings and representations
      Ministry of Science and Higher Education
      as a part of EUROCORES program: Graphs in Geometry and Algorithms (EuroGIGA), maintained by European Science Foundation
    2012 - 2014 Coloring games on graphs and partially ordered sets
      Polish National Science Center
      MO-2011/03/B/ST6/01367
    2012 - 2015 Graph sharing games: strategies and algorithms
      Polish National Science Center
      UMO-2011/03/N/ST6/03111

    short cv
    2008Software Engineer Intern (3 months)Google Switzerland GmbHZürich, Switzerland
    2008MSc (computer science)Jagiellonian UniversityKraków, Poland
    2012PhD (computer science)Jagiellonian UniversityKraków, Poland
    2013-14Postdoctoral Research Fellow (12 months)École Polytechnique Fédérale de LausanneLausanne, Switzerland
    2014Mobility Plus Research Fellow (6 months)Charles UniversityPrague, Czech Republic
    2014-15Visiting Assistant Professor (9 months)Georgia Institute of TechnologyAtlanta, USA
     
     
      webmaster: email = a@b, a=www-tcs, b=tcs.uj.edu.pl