Redrawing a Graph within a Geometric Tolerance

Abellanas, 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, Princeton, New Jersey, USA , pp. 246-253 (Official URL: http://dx.doi.org/10.1007/3-540-58950-3_376).

Full text not available from this repository.

Abstract

In 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-58950-3_376
Classifications:Z Theory > Z.250 Geometry
G Algorithms and Complexity > G.560 Geometry
P Styles > P.999 Others
ID Code:186

Repository Staff Only: item control page

References

M. Abellanas, J. García, G. Hernàndez, F. Hurtado, O. Serra, J. Urrutia: Updating polygonizations, Computer Graphics Forum, vol.12, n.3 (1993), pp.143-152.

M. Abellanas, F. Hurtado, P. Ramos: Tolerance of geometric structures, Proc. 6th Canadian Conference on Computational Geometry (1994).

P.J. Agarwal, M. Sharir, S. Toledo: Applications of parametric searching in geometric optimization, Proc. 3rd ACM-SIAM Symposium on Discrete Algorithms (1992), pp. 72-82.

F. Aurenhammer: Improved algorithms for discs and balls using powerd iagrams, Journal of Algorithms 9 (1988), pp. 151-161.

K.Q. Brown: Geometric transforms for fast geometric algorithms, Ph.D. thesis, Rep. CMU-CS-80-101, Dept. of Computer Science, Carnegie-Mellon Univ., Pittsburgh (1980).

P. Eades, R. Tamassia: Algorithms for drawing graphs: An Annotated bibliography, Technical Report, Dept. of Computer Science, Brown Univ., Providence, Rhode Island (1989).

P. Eades, W. Lai, K. Misue, K. Sugiyama: Preserving the Mental Map of a Diagram Research Report IIAS-RR-91-16E, International Institute for Advanced Study of Social Information Science, Fujitsu Laboratories Ltd., 17-25, Shinkamata 1-chome, Ohta-ku, Tokyo 144, Japan, August 1991.

K.A. Lyons: Cluster Busting in Anchored Graph Drawing Ph.D. thesis, Queen's University (1994).

K.A. Lyons, H. Meijer, D. Rappaport: Properties of the Veronoi Diagram Cluster Buster Proc. 1993 CAS Conference (CASCON'93) Vol. II, A. Gawman, W.M. Getleman, E. Kidd, P.Larson, J. Slonim, Eds, IBM Canada Ltd. Laboratory Center for Advanced Studies and NRC Canada, Toronto (Canada), October 24-28 1993, pp. 1148-1163.

P. Ramos: Tolerancia de Estructuras Geométricas y Combinatorias Ph.D. Thesis (in spanish), in preparation.