12 citations · 32 across the 8 of their papers we have counts for
13 papers
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…
On the queue-number of graphs with bounded tree-width
Veit Wiechert
A queue layout of a graph consists of a linear order on the vertices and an assignment of the edges to queues, such that no two edges in a single queue are nested. The minimum numb…
A minimum-change version of the Chung-Feller theorem for Dyck paths
Torsten Mütze, Christoph Standke, Veit Wiechert
A Dyck path with steps and flaws is a path in the integer lattice that starts at the origin and consists of many -steps and many -steps that ch…
Grid Intersection Graphs and Order Dimension
Steven Chaplick, Stefan Felsner, Udo Hoffmann +1
We study subclasses of grid intersection graphs from the perspective of order dimension. We show that partial orders of height two whose comparability graph is a grid intersection…
Sparsity and dimension
Gwenaël Joret, Piotr Micek, Veit Wiechert
We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Nešetřil and Osson…
Topological minors of cover graphs and dimension
Piotr Micek, Veit Wiechert
We show that posets of bounded height whose cover graphs exclude a fixed graph as a topological minor have bounded dimension. This result was already proven by Walczak. However, ou…
An on-line competitive algorithm for coloring bipartite graphs without long induced paths
Piotr Micek, Veit Wiechert
The existence of an on-line competitive algorithm for coloring bipartite graphs remains a tantalizing open problem. So far there are only partial positive results for bipartite gra…
A note on concurrent graph sharing games
Steven Chaplick, Piotr Micek, Torsten Ueckerdt +1
In the concurrent graph sharing game, two players, called First and Second, share the vertices of a connected graph with positive vertex-weights summing up to as follows. The g…
On the dimension of posets with cover graphs of treewidth
Gwenaël Joret, Piotr Micek, William T. Trotter +2
In 1977, Trotter and Moore proved that a poset has dimension at most whenever its cover graph is a forest, or equivalently, has treewidth at most . On the other hand, a well…