One strike against the min-max degree triangulation problem (Q685602)

From MaRDI portal
scientific article
Language Label Description Also known as
English
One strike against the min-max degree triangulation problem
scientific article

    Statements

    One strike against the min-max degree triangulation problem (English)
    0 references
    0 references
    17 October 1993
    0 references
    The min-max degree triangulation problem is the following: Given a finite plane geometric graph \(G\) in \(R^ 2\), and an integer \(k\), is there a triangulation \(G'\) of \(G\) with maximum degree \(\leq k\)? The author shows that this problem is NP-complete for \(k\leq 7\).
    0 references
    triangulation
    0 references
    geometric graph
    0 references
    NP-complete
    0 references

    Identifiers