Name
Abstract | ||
|---|---|---|
In this paper we study the problem of triangulating a planar graph G while minimizing the maximum degree (G) of the resulting triangulated planar graph G. It is shown that this problem is NP-complete. Worst-case lower bounds for (G) with respect to (G) are given. We describe a linear algorithm to triangulate planar graphs, for which the maximum degree of the triangulated graph is only a constant larger than the lower bounds. Finally we show that triangulating one face while minimizing the maximum degree can be achieved in polynomial time. We use this algorithm to obtain a polynomial exact algorithm to triangulate the interior faces of an outerplanar graph while minimizing the maximum degree. |
Year | DOI | Venue |
|---|---|---|
1992 | 10.1006/inco.1997.2635 | Information and Computation/information and Control |
Keywords | DocType | Volume |
maximum degree,triangulating planar graphs,planar graph,lower bound,outerplanar graph,polynomial time | Conference | 135 |
Issue | ISSN | ISBN |
1 | Information and Computation | 3-540-55706-7 |
Citations | PageRank | References |
15 | 2.09 | 19 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Goos Kant | 1 | 565 | 51.19 |
| Hans L. Bodlaender | 2 | 5699 | 375.15 |