pith. sign in

arxiv: 1809.02710 · v1 · pith:VN7M542Ynew · submitted 2018-09-07 · 💻 cs.CG

The Partition Spanning Forest Problem

classification 💻 cs.CG
keywords forestpointsclasscolorcontainseveryproblemspanning
0
0 comments X
read the original abstract

Given a set of colored points in the plane, we ask if there exists a crossing-free straight-line drawing of a spanning forest, such that every tree in the forest contains exactly the points of one color class. We show that the problem is NP-complete, even if every color class contains at most five points, but it is solvable in $O(n^2)$ time when each color class contains at most three points. If we require that the spanning forest is a linear forest, then the problem becomes NP-complete even if every color class contains at most four points.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.