2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Apr 4 '14 at 21:42
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Apr 4 '14 at 22:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.