Approximate proximity drawings
type: Item
instance of: scholarly article
title: Approximate proximity drawings
zbMATH Open document ID: 1267.65025
author: Michael Kaufmann
author: Giuseppe Liotta
author: Andreas Spillner
author: W. Evans
author: Emden R. Gansner
author: Henk Meijer
published in: Computational Geometry
publication date: 2013-04-29T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 65D18
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 6159331
zbMATH Keywords: graph drawing
zbMATH Keywords: Gabriel graphs
zbMATH Keywords: beta skeletons
zbMATH Keywords: Delaunay triangulation
reviewed by: H. P. Dikshit
Wikidata QID: Q62042418
MaRDI profile type: Publication
full work available at URL: j.comgeo.2013.01.001
OpenAlex ID: W1991522034
cites work: On the Area Requirements of Euclidean Minimum Spanning Trees
cites work: Witness (Delaunay) graphs
cites work: Witness Rectangle Graphs
cites work: Witness Gabriel graphs
cites work: Characterizing proximity trees
cites work: How to draw a planar graph on a grid
cites work: The strength of weak proximity
cites work: Drawing a tree as a minimum spanning tree approximation
cites work: The Approximate Rectangle of Influence Drawability Problem
cites work: Toughness and Delaunay triangulations
cites work: A simple method for resolving degeneracies in Delaunay triangulations
cites work: Approximate Proximity Drawings
DOI: 10.1016/J.COMGEO.2013.01.001
description: scientific article; zbMATH DE number 6159331