P250: Enumeration of all non-crossing spanning trees on a given point set in the plane

P250: Enumeration of all non-crossing spanning trees on a given point set in the plane

Input:

A fixed point set $P$.

Output:

All non-crossing spanning trees on $P$.

Complexity:

$O(N + |P|tri(P))$ total time.

Comment:

$N$ is the number of solutions and $tri(P)$ is the number of triangulations of $P$.

Reference:

[Katoh2009a] (Bibtex)