Tim Planken Personal Website

Open problems

A selection of open problems that I find particularly interesting.

Computing tetra- and cactus-decompositions

A graph in black, with blue bags and a red decomposition cactus.
A cactus-decomposition of a 2-connected graph.

The classical Tutte-decomposition can be computed in linear time. Can its extensions to higher connectivity also be computed efficiently?

Conjecture (tetra-decomposition). There is an algorithm that computes the tetra-separation decomposition of any finite 4-connected graph in linear time.

See Conjecture 1.4 in my paper with Jan Kurkofka, A Tutte-type canonical decomposition of 3- and 4-connected graphs (arXiv), SODA 2026.

For every k, our approximate cactus-decomposition represents all k-separations of a k-connected graph up to an error bounded in terms of k.

Question (cactus-decomposition). For fixed k, can the approximate cactus-decomposition for k-connected graphs from our paper be computed in linear time?

See Conjecture 1.3 in my paper with Romain Bourneuf, Johannes Carmesin and Jan Kurkofka, An approximate cactus-decomposition for vertex-connectivity (arXiv).

Colouring 2-complexes in 3-space

A tetrahedron with its inner chamber subdivided, and edges coloured red, blue and green.

Question. Can the edges of every finite simplicial 2-complex embedded in ℝ3 be coloured with three colours so that every triangular face has edges of at least two colours?

Known bounds. Four colours always suffice, and some embedded simplicial 2-complexes cannot be coloured with two colours without a monochromatic face. Hence the smallest number of colours that works for all such complexes is either three or four.

See Question 8.1 in my paper Colouring the 1-skeleton of d-dimensional triangulations (journal version), Innovations in Graph Theory 2 (2025), 275–299.

Shallow hitting sets and polychromatic colourings for squares

Points coloured with three colours and four axis-aligned squares, each containing five points and all three colours.

All squares below are axis-aligned and may have arbitrary side lengths.

Question (shallow hitting sets). Is there an absolute constant t such that, for every finite P ⊆ ℝ2 and every integer m ≥ 1, there is a subset S ⊆ P for which every square containing exactly m points of P contains at least one and at most t points of S?

Question (polychromatic colourings). Is there an absolute constant C such that, for every finite P ⊆ ℝ2 and every integer k ≥ 2, the points of P can be coloured with k colours so that every square containing at least Ck points of P contains all k colours?

A positive answer to the first question would imply a positive answer to the second.

See Table 1 and Section 5 in my paper with Torsten Ueckerdt, Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets (conference version), SoCG 2024, 293, 74:1–74:14.

Solved problems

Shallow hitting edge sets in regular hypergraphs

A set of edges in a hypergraph is a t-shallow hitting edge set if every vertex belongs to at least one and at most t of the selected edges.

Question. Is there an absolute constant C such that, for every integer r ≥ 2, every finite r-uniform regular hypergraph has a (C log r)-shallow hitting edge set?

In our paper, we proved a logarithmic lower bound and a linear upper bound for the smallest guaranteed shallowness.

See Section 5 in my paper with Torsten Ueckerdt, Shallow Hitting Edge Sets in Uniform Hypergraphs (arXiv).

Solved (2026). Noga Alon, Penny Haxell, Aleksa Milojević and Jacques Verstraëte proved the following.

Theorem. For every integer r ≥ 2, every finite r-uniform regular hypergraph has a (100 log r)-shallow hitting edge set.

Together with our lower bound, this establishes that the optimal guaranteed shallowness has order Θ(log r).

See Theorem 1.2 in Spanning subhypergraphs with degree constraints (arXiv).