5 papers · 1 filter
Boxicity, poset dimension, and excluded minors
Louis Esperet, Veit Wiechert
In this short note, we relate the boxicity of graphs (and the dimension of posets) with their generalized coloring parameters. In particular, together with known estimates, our res…
Realization of shift graphs as disjointness graphs of 1-intersecting curves in the plane
Torsten Mütze, Bartosz Walczak, Veit Wiechert
It is shown that shift graphs can be realized as disjointness graphs of 1-intersecting curves in the plane. This implies that the latter class of graphs is not -bounded.
Nowhere Dense Graph Classes and Dimension
Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez +1
Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained ov…
Burling graphs, chromatic number, and orthogonal tree-decompositions
Stefan Felsner, Gwenaël Joret, Piotr Micek +2
A classic result of Asplund and Grünbaum states that intersection graphs of axis-aligned rectangles in the plane are -bounded. This theorem can be equivalently stated in terms o…
Planar posets have dimension at most linear in their height
Gwenaël Joret, Piotr Micek, Veit Wiechert
We prove that every planar poset of height has dimension at most . This improves on previous exponential bounds and is best possible up to a constant factor. We…