CABELLO JUSTO , Sergio

Let G = (V, E) be a graph with n vertices and let P be a set of n points in the plane. We show that deciding whether there is a planar straight-line embedding of G such that the vertices V are embedded onto the points P is NP-complete, even when G is 2-connected and 2-outerplanar. This settles an open problem posed in [P. Bose. On embedding an...

Let A and B be two sets of n resp. m (m ≥ n) disjoint unit disks in the plane. We consider the problem of finding a rigid motion of A that maximizes the total area of its overlap with B. The function describing the area of overlap is quite complex, even for combinatorially equivalent translations, and hen e, we turn our attention to...

Let G be a graph embedded in an orientable surface Σ, possibly with edge weights, and denote by len(γ) the length (the number of edges or the sum of the edge weights) of a cycle γ in G. The stretch of a graph embedded on a surface is the minimum of len(α)· len(β) over all pairs of cycles α and β that cross exactly once. We provide an algorithm...