Tom van der Zanden

Welcome to my home page! On June 26th, I defended my PhD thesis "Theory and Practical Applications of Treewidth" (pdf), which I completed under the supervision of Hans Bodlaender at Utrecht University. I am interested in the theory and applications of graph algorithms (specifically those involving treewidth) and parameterized and exact complexity. As a hobby, I design and make 3D printed puzzles (and recently, other 3D printed and electronic gadgets). As of October 2019, I am Assistant Professor in Algorithms and Optimisation at the Department of Data Analytics and Digitalisation of Maastricht University.

You can reach me via my institutional mail (T.vanderZanden@maastrichtuniversity.nl) or personal email address (tom@tomvanderzanden.nl).
If you would like to buy one of my puzzles, you can do so in my Shapeways shop (beware of sticker shock, Shapeways has regretfully raised their prices a lot compared to what they used to be).

Publications

Google Scholar - dblp

Below is a list of my (peer-reviewed) conference publications.

  • On Exploring Always-Connected Temporal Graphs of Small Pathwidth - joint work with Hans Bodlaender. Information Processing Letters (2019). arXiv
  • Flower power: Finding Optimal Flower Cutting Strategies Through a Combination of Optimization and Data Mining - joint work with Han Hoogeveen and Jakub Tomczyk. Computers & Industrial Engineering (2019).
  • Subgraph Isomorphism on Graph Classes that Exclude a Substructure - joint work with Hans Bodlaender, Tesshu Hanaka, Yoshio Okamoto and Yota Otachi. CIAC 2019, to appear.
  • Stable Divisorial Gonality is in NP - joint work with Hans Bodlaender and Marieke van der Wegen. SOFSEM 2019. arXiv
  • On the Exact Complexity of Polyomino Packing - joint work with Hans Bodlaender. FUN 2018.
  • Framework for ETH-tight algorithms and lower bounds in geometric intersection graphs - joint work with Mark de Berg, Hans Bodlaender, fellow PhD-student Sándor Kisfaludi-Bak and Daniel Marx. STOC 2018. arXiv
  • Complexity of the Maximum k-Path Vertex Cover Problem - joint work with Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara and Tsuyoshi Yagita. WALCOM 2018.
  • Computing Treewidth on the GPU - joint work with Hans Bodlaender. IPEC 2017. arXiv
  • On the Exact Complexity of Hamiltonian Cycle and q-Colouring in Disk Graphs - joint work with Sándor Kisfaludi-Bak. CIAC 2017.
  • Improved Lower Bounds for Graph Embedding Problems - joint work with Hans Bodlaender. Best paper award at CIAC 2017. arXiv
  • On the Maximum Weight Minimal Separator - joint work with Tesshu Hanaka, Hans Bodlaender and Hirotaka Ono. TAMC 2017.
  • Subexponential Time Algorithms for Embedding H-Minor Free Graphs - joint work with Hans Bodlaender and Jesper Nederlof. ICALP 2016.
  • Parameterized Complexity of Graph Constraint Logic - single author paper. IPEC 2015. arXiv
  • PSPACE-Completeness of Bloxorz and of Games with 2-Buttons - joint work with Hans Bodlaender. CIAC 2015. arXiv
  • According to google scholar, my H-index is 5. My Erdős number is 3 (via Hans Bodlaender); my Erdős lap number is 4 (via Ryhuei Uehara).

    Software

  • PartStacker - Create tight packings of (puzzle) parts to minimize the cost of having them 3D printed.
  • SteinerTreeTW (github) - Steiner Tree solver using dynamic programming on tree decompositions. Submission to the PACE 2018 challenge (third place).
  • GPGPU Treewidth (github) - Compute tree decompositions on a GPU. Associated paper at IPEC 2017.
  • BZTreewidth (github) - Solver for computing tree decompositions. Submission to the PACE 2016 challenge (second place).
  • Teaching

    I am very interested in teaching. My current teaching duties at Utrecht University include assisting in the Algorithms course and in the Concurrency course.
    For the algorithms course, I lead the working classes and handle the practical programming assignments through the automatic grading system DomJudge (thinking up the assignments, generating test cases, writing a reference solution and helping the students debug their code).
    For concurrency, I also lead the working classes and handle the practical programming assignments through a DomJudge knockoff called "TomJudge" (which includes some features specific to concurrency, such as automatically measuring whether the program executes faster given more cores).
    I also am the administrator of our department's DomJudge installation, which, besides its use in algorithms, is also used in many other courses. I help lecturers set up their assignments, handle any problems that come up, and occasionally develop new features. I recently gave a presentation on our use of DomJudge at the Dutch ICT education symposium NIOC 2018.

    Puzzles

    Below you can see some of the puzzles that I have designed. You can click on a puzzle to get more information about it. Each of these puzzles was designed using 3D CAD software, and then printed by Shapeways in Nylon using Selective Laser Sintering (SLS). I dye the puzzles myself (using dylon ebony black dye) and make my own stickers on a plotter. Note that several of these puzzles have been mass produced (either by Mefferts, MF8 or Calvin's Puzzles).

    Switch Cube very difficult custom Rubikexclusive fully functional 3x4x5 cuboid very hard and difficult custom RubikDeep Unaxial 3x3x3 Rubik3x3x3 Dino Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftCurvy Copter plus Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle gift like Helicopter Cube by Adam G CowanCurvy Copter II very difficult custom Rubiks cube type twisty puzzle like the Mefferts Helicopter Cube by Adam G. CowanHoley Octahedron custom Rubiks cube type twisty puzzle like Gentoshas Void Cube by Okamoto
    4x4x6 Cuboid rare mass produced Rubik3x3x3 RubikCurvy Copter very difficult custom Rubik3x3x3 Rainbow Cube very difficult custom Rubiks cube type twisty puzzle a combination of the Rainbow Cube and original 3x3x3 Rubiks CubeConstrained Cube Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftDino Skewb very difficult custom Rubiks cube type twisty puzzle a combination of the Dino Cube and Mefferts Skewb1x2x3 cuboid fun and easy cheap custom Rubik
    Chimera 4x4 and 6x6 combination cube very hard and difficult custom RubikMultidodecahedron - Megaminx and Master Pentultimate in one, Brilic / Pyraminx Crystal, Hungarian Supernova, Starminx, Pentultimate hybrid, twisty puzzle RubikMaster Face Turning Octahedron FTO RubikMini Pentultimate dodecahedron Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftHelicopter Skewb Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftMaster Brilic very difficult custom Rubiks cube type twisty puzzle like the Gigaminx and Mefferts Pyraminx Crystal puzzle
    6x6x7 Cuboid custom Rubik4x5x6 Cuboid shapeshifting 3x4x5 fully functional RubikOffset Skewb 2x2x2 puzzle Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftMini Starminx dodecahedron Rubiks Cube variation very difficult custom Rubiks cube type twisty puzzle giftCompy Skewb very difficult custom Rubiks cube type twisty puzzle a combination of the Compy Cube/shallow cut Dino Cube and Mefferts SkewbTetrahedral Twins special custom stella octangula Rubik