Approximate proximity drawings (Q1947972)

The paper is devoted to approximate Gabriel drawings (see [\textit{P. Bose} et al., Algorithmica 16, No. 1, 83--110 (1996; Zbl 0855.68068)]), to approximate \(\beta\) -drawings and to approximate Delaunay drawings. The main contribution of the present paper is in introducing the concept of \((\epsilon_1, \epsilon_2)\)-proximity drawings and in proving the existence of such drawings for relevant families of graphs. It is shown that each of the foregoing types of drawings allows, for any embedded planar graph \(G\), an embedding preserving \((\epsilon_1, \epsilon_2)\)-proximity drawing of \(G\), as long as both the parameters \(\epsilon_1\) and \(\epsilon_2\) are strictly positive. This does not continue to hold true if \(\epsilon_1\) or \(\epsilon_2\) is zero. In particular, \((0, \epsilon_2)\)-Gabriel drawings of outerplanar graphs extend some earlier results of \textit{G. Di Battista} et al. [J. Discrete Algorithms 4, No. 3, 384--400 (2006; Zbl 1102.65022)].