<p>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.</p>

<p>I cam across this page <a href="http://cs.anu.edu.au/~bdm/plantri/" rel="nofollow">http://cs.anu.edu.au/~bdm/plantri/</a> which implements a program to do the above but the algorithm was not clear to me.</p>

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

CC BY-SA 3.0
2014-04-04T21:42:40.823Z
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
CC BY-SA 3.0
2014-04-04T22:02:37.490Z
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
<graph-algorithms><computational-geometry>
Eulerian Triangulations
Dibyayan
# Eulerian Triangulations

(Asked by: username_0 on 2014-04-04)

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.

**Tags:** graph-algorithms, computational-geometry
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  

---

## 0 answers

