Now showing items 1-10 of 43
Monotone crossing number of complete graphs [Presentation]
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 ...
Phase transitions in the Ramsey-Turán theory [Presentation]
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 ...
On 4-connected geometric graphs [Presentation]
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.
Flips in combinatorial pointed pseudo-triangulations with face degree at most four [Presentation]
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 ...
Reporting flock patterns on the GPU [Presentation]
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 ...
Solving common influence region queries with the GPU [Presentation]
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 ...
Guarding the vertices of thin orthogonal polygons is NP-hard [Presentation]
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 ...
Three location tapas calling for CG sauce [Presentation]
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.
On the barrier-resilience of arrangements of ray-sensors [Presentation]
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 ...