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

From MaRDI portal
Set OpenAlex properties.
ReferenceBot (talk | contribs)
Changed an Item
 
Property / cites work
 
Property / cites work: Constrained Delaunay triangulations / rank
 
Normal rank
Property / cites work
 
Property / cites work: Delaunay graphs are almost as good as complete graphs / rank
 
Normal rank
Property / cites work
 
Property / cites work: A sweepline algorithm for Voronoi diagrams / rank
 
Normal rank
Property / cites work
 
Property / cites work: Two algorithms for constructing a Delaunay triangulation / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q3992847 / rank
 
Normal rank
Property / cites work
 
Property / cites work: Constructing the visibility graph for n-line segments in \(O(n^ 2)\) time / rank
 
Normal rank

Latest revision as of 09:50, 20 June 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