In 1958, Hill conjectured that the minimum number of crossings in a drawing of Kn is exactly Z(n) = 1/4 n-1/2/2 n−2/2 n−3/2. Generalizing the result by Ábrego et al. for 2-page book drawings, we prove this conjecture for ...

Let f(n) be a function and L be a graph. Denote by RT(n, L, f(n)) the maximum number of edges of an L-free graph on n vertices with independence number less than f(n). Erdos and Sós asked if RT (n, K5, c√ n) = o (n2) for ...

Given a set S of n points in the plane, in this paper we give a necessary and sometimes sufficient condition to build a 4-connected non-crossing geometric graph on S.

In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric ...

In this paper we study the problem of finding flock patterns in a set of trajectories of moving entities. A flock refers to a large enough subset of entities that move close to each other for a given time interval. We present ...

In this paper we propose and solve common influence region queries. We present GPU parallel algorithms, designed under CUDA architecture, for approximately solving the studied queries. We also provide and discuss experimental ...

An orthogonal polygon of P is called “thin” if the dual graph of the partition obtained by extending all edges of P towards its interior until they hit the boundary is a tree. We show that the problem of computing a minimum ...

Based on some recent modelling considerations in location theory we call for study of three CG constructs of Voronoi type that seem not to have been studied much before.

Given an arrangement A of n sensors and two points s and t in the plane, the barrier resilience of A with respect to s and t is the minimum number of sensors whose removal permits a path from s to t such that the path ...