35 citations · 45 across the 3 of their papers we have counts for
4 papers
Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness
Janos Barat, Jiri Matousek, David R. Wood
The geometric thickness of a graph G is the minimum integer k such that there is a straight line drawing of G with its edge set partitioned into k plane subgraphs. Eppstein [Separa…
Expected length of the longest common subsequence for large alphabets
Marcos Kiwi, Martin Loebl, Jiri Matousek
We consider the length L of the longest common subsequence of two randomly uniformly and independently chosen n character words over a k-ary alphabet. Subadditivity arguments yield…
Topological lower bounds for the chromatic number: A hierarchy
Jiri Matousek, Günter M. Ziegler
This paper is a study of ``topological'' lower bounds for the chromatic number of a graph. Such a lower bound was first introduced by Lovász in 1978, in his famous proof of the \em…
Almost-tiling the plane by ellipses
Krystyna Kuperberg, Włodzimierz Kuperberg, Jiří Matoušek +1
For any delta > 1 we construct a periodic and locally finite packing of the plane with ellipses whose delta-enlargement covers the whole plane. This answers a question of Imre Bárá…