The Strength of Weak Proximity (Extended Abstract)Di Battista, Giuseppe and Liotta, Giuseppe and Whitesides, Sue (1996) The Strength of Weak Proximity (Extended Abstract). In: Symposium on Graph Drawing, GD 1995, September 2022, 1995 , pp. 178189(Official URL: http://dx.doi.org/10.1007/BFb0021802). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/BFb0021802
AbstractThis paper initiates the study of weak proximity drawings of graphs and demonstrates their advantages over strong proximity drawings in certain cases. Weak proximity drawings are straight line drawings such that if the proximity region of two points p and q representing vertices is devoid of other points representing vertices, then segment (p,q) is allowed, but not forced, to appear in the drawing. This differs from the usual, strong, notion of proximity drawing in which such segments must appear in the drawing. Most previously studied proximity regions are associated with a parameter \beta, 0\le\beta\le\infty. For fixed \beta, weak \betadrawability is at least as expressive as strong \betadrawability, as a strong \betadrawing is also a weak one. We give examples of graph families and \beta values where the two notions coincide, and a situation in which it is NPhard to determine weak \betadrawability. On the other hand, we give situations where weak proximity significantly increases the expressive power of \betadrawability: we show that every graph has, for all sufficiently small \beta, a weak \betaproximity drawing that is computable in linear time, and we show that every tree has, for every \beta less than 2, a weak \betadrawing that is computable in linear time.
Actions (login required)
