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
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
