There are planar graphs almost as good as the complete graph
type: Item
instance of: scholarly article
title: There are planar graphs almost as good as the complete graph
zbMATH Open document ID: 0682.05032
DOI: 10.1016/0022-0000(89)90044-5
author: L. Paul Chew
published in: Journal of Computer and System Sciences
publication date: 1989-01-01T00:00:00Z
review text: For a graph G represented in the plane (perhaps with edges intersecting internally) the length of a path joining two vertices of G is here regarded as the sum of the straight-line distances between successive vertices on the path. Given a set S of points in the plane, the complete graph on S has the property that for each pair A, B in S there exists an A-B path of length the straight-line distance between A and B. (The complete graph is unique with this property, if the points of S are in general position.) In this paper it is shown that there is a planar graph G on S with the property: for each pair A, B in S, there exists an A-B path of length at most twice the straight-line distance between A and B. The graph G is a type of Delaunay triangulation. It has 0 (ISI) edges (compare 0 \((ISI^ 2)\) for the complete graph). Applications are discussed to network design and motion planning.
Mathematics Subject Classification ID: 05C10
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 4116563
zbMATH Keywords: length of a path joining two vertices
zbMATH Keywords: planar graph
zbMATH Keywords: straight-line distance
zbMATH Keywords: Delaunay triangulation
reviewed by: Arthur T. White
MaRDI profile type: Publication
full work available at URL: 0022-0000(89)90044-5
OpenAlex ID: W2139391136
cites work: Constrained Delaunay triangulations
cites work: Delaunay graphs are almost as good as complete graphs
cites work: A sweepline algorithm for Voronoi diagrams
cites work: Two algorithms for constructing a Delaunay triangulation
cites work: Q3992847
cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time
description: scientific article; zbMATH DE number 4116563