# Eulerian Triangulations

Hi i am looking for algorithms to decide whether a planar pointset has a eulerian triangulation i.e. a triangulation that makes every vertex of even degree.

I cam across this page http://cs.anu.edu.au/~bdm/plantri/ which implements a program to do the above but the algorithm was not clear to me.

Any idea to design algorithm for the above problem will be helpfull. Any link/paper to easier discussion is also welcome.

• I think McKay's plantri solves a different problem: listing all combinatorially distinct Eulerian triangulations with a given number of vertices as abstract graphs. I don't think it makes reference to a geometric embedding of these graphs. – David Eppstein Apr 4 '14 at 21:42
• Also, it's not hard to prove that a convex point set has an Eulerian triangulation iff its number of vertices is divisible by three. However that does not generalize; for instance there exists an Eulerian triangulation of the seven points formed by a regular hexagon and its center. – David Eppstein Apr 4 '14 at 22:02