There are planar graphs almost as good as the complete graph (Q1823959): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/0022-0000(89)90044-5 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2139391136 / rank | |||
Normal rank |
Revision as of 20:16, 19 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | There are planar graphs almost as good as the complete graph |
scientific article |
Statements
There are planar graphs almost as good as the complete graph (English)
0 references
1989
0 references
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.
0 references
length of a path joining two vertices
0 references
planar graph
0 references
straight-line distance
0 references
Delaunay triangulation
0 references