67 citations · 377 across the 34 of their papers we have counts for
6 papers · 1 filter
Decomposition of multiple packings with subquadratic union complexity
János Pach, Bartosz Walczak
Suppose is a positive integer and is a -fold packing of the plane by infinitely many arc-connected compact sets, which means that every point of the plane belo…
Outerstring graphs are -bounded
Alexandre Rok, Bartosz Walczak
An outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane. We prove that the class of outerst…
Coloring intersection graphs of arc-connected sets in the plane
Michał Lasoń, Piotr Micek, Arkadiusz Pawlik +1
A family of sets in the plane is simple if the intersection of its any subfamily is arc-connected, and it is pierced by a line if the intersection of its any member with is…
New bounds on the maximum number of edges in -quasi-planar graphs
Andrew Suk, Bartosz Walczak
A topological graph is -quasi-planar if it does not contain pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed , the maximum number of edges i…
Tree-width and dimension
Gwenaël Joret, Piotr Micek, Kevin G. Milans +3
Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural grap…
Coloring triangle-free rectangle overlap graphs with colors
Tomasz Krawczyk, Arkadiusz Pawlik, Bartosz Walczak
Recently, it was proved that triangle-free intersection graphs of line segments in the plane can have chromatic number as large as . Essentially the same constru…