Models and algorithms to compute proximity drawings of graphs.
A proximity drawing is a straight-line drawing that is constructed by connecting with an edge every pair of points of a given point-set that are close enough to each other, according to some definition of closeness. Of course, the same point-set can give rise to many different proximity drawings when different closeness measures are used.
Proximity drawings are a main topic in Computational Geometry and find their main applications in areas where it is needed to describe the underlying shape of a set of points, like Computer Graphics, Pattern Recognition, Numerical Analysis, and Computational Biology.
We mainly deal with proximity drawings from the Graph Drawing perspective, which is different from the Computational Geometry one. Namely, we consider problems in which a graph G and a proximity measure P are given and the goal is to construct a straight-line drawing of G that is a proximity drawing with respect to P. We consider such problems in terms of defintion of algorithms to construct proximity drawings, of characterization of classes of graphs that admit proximity drawings, and of area requirements for this drawing style.
Famous examples of proximity drawings and of proximity graphs, that is, graphs that are obtained from a given point set when a certain proximity measure has been defined, are Gabriel graphs, Delaunay Triangulations, Minimum Spanning Trees, and Greedy Drawings.