We show that there is a linear-time algorithm to partition the edges of a planar graph into triangles. We show that the problem is also polynomial for toroidal graphs but NP-complete for k-planar graphs, where k is at least 8.
Comments: 15 Pages.
[v1] 2012-09-17 05:15:21
Unique-IP document downloads: 67 times
Add your own feedback and questions here: