Linear vertex deletion conjecture for bounded boxicity of surface graphs

Let GG be a graph embedded on a surface of Euler genus gg. The boxicity of a graph is the minimum dimension in which it can be represented as the intersection graph of axis-parallel boxes.

Linear vertex deletion conjecture. There is a constant c>0c>0 such that, for every graph GG embedded on a surface of Euler genus gg, at most cgcg vertices can be removed so that the resulting graph has boxicity at most 33.

The conjecture is a surface-graph variant of the preceding conjecture for locally planar graphs. The supplied source gives no evidence that it has been resolved; it would in particular provide a linear-size deletion bound depending on the Euler genus.

Sources & referencesView supporting material

Primary source

Louis Esperet, “Box representations of embedded graphs”, arXiv:1512.02381 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.