5 papers
Ordered Yao graphs: maximum degree, edge density, and clique numbers
Péter Ãgoston, Adrian Dumitrescu, Arsenii Sagdeev +2
For a positive integer and an ordered set of points in the plane, define its \textit{k-sector ordered Yao graphs} as follows. Divide the plane around each point into eq…
Rado's covering problem for cubes and balls: a semi-survey
Gian Maria Dall'Ara, Adrian Dumitrescu
What is the largest constant with the property that every finite collection of axis-parallel squares in the plane admits a disjoint sub-collection $\math…
Finding Small Complete Subgraphs Efficiently
Ke Chen, Adrian Dumitrescu, Andrzej Lingas
(I) We revisit the algorithmic problem of finding all triangles in a graph with vertices and edges. According to a result of Chiba and Nishizeki (1985), this task…
Maximal Distortion of Geodesic Diameters in Polygonal Domains
Adrian Dumitrescu, Csaba D. Tóth
For a polygon with holes in the plane, we denote by the ratio between the geodesic and the Euclidean diameters of . It is shown that over all convex polygons wi…
Lattice and Non-lattice Piercing of Axis-Parallel Rectangles
Adrian Dumitrescu, Arsenii Sagdeev, Josef Tkadlec
Given a family of shapes in the plane, we study what is the lowest possible density of a point set that pierces (``intersects'', ``hits'') all translates of each…