There are planar graphs almost as good as the complete graph (Q1823959): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Changed an Item
Import240304020342 (talk | contribs)
Set profile property.
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank

Revision as of 04:48, 5 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
    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

    Identifiers