There are planar graphs almost as good as the complete graph (Q1823959): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 10:51, 1 February 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