Redrawing a Graph within a Geometric ToleranceAbellanas, Manuel and Hurtado, Ferran and Ramos, Pedro (1995) Redrawing a Graph within a Geometric Tolerance. In: Graph Drawing DIMACS International Workshop, GD 1994, October 10–12, 1994 , pp. 246253(Official URL: http://dx.doi.org/10.1007/3540589503_376). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/3540589503_376
AbstractIn this paper we investigate some applications of the concept of tolerance to graph drawing. Given a geometric structure, the tolerance is a measure of how much the set of points can be arbitrarily changed while preserving the structure. Then, if we have a layout of a graph and we want to redraw the graph while preserving the mental map (captured by some proximility graph of the set of nodes), the tolerance of this proximity graph can be a useful tool. We present an optimal O(n log n) algorithm for computing the tolerance of the Delaunay triangulation of a set of points and propose some variations with applications to interactive environments.
Actions (login required)
