NP-hardness conjecture for the bicolored MST crossing number

Less than 1 year old · traced to

Let PP be a finite point set in the plane, and let cr-MST⁡(P)\operatorname{cr-MST}(P) denote its bicolored minimum spanning tree crossing number. The NP-hardness conjecture. Finding cr-MST⁡(P)\operatorname{cr-MST}(P) is NP-hard.

This concerns the computational complexity of the bicolored MST crossing number. The paper presents NP-hardness as a conjecture and gives no proof or resolution.

References

Primary source

Todor Antić, Morteza Saghafian, Maria Saumell, Felix Schröder, Josef Tkadlec and Pavel Valtr, “How many times can two minimum spanning trees cross?”, arXiv:2601.20060 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.