<p>A <a href="http://en.wikipedia.org/wiki/Planar_graph" rel="noreferrer">plane graph</a> $G$ defines a cyclic ordering $O(v) = \langle v_1, v_2, \dotsc, n_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an <a href="http://en.wikipedia.org/wiki/Eulerian_path" rel="noreferrer">Eulerian circuit</a> such that for every vertex $v \in V(G)$ and every choice of four edges $\{a,v\}, \{b,v\}, \{c,v\}, \{d,v\} \in E(G)$ containing $v$, if the cyclic ordering $O(v)$ restricted to $\{a,b,c,d\}$ is $\langle a,b,c,d \rangle$ and $\{a,c\} \in C$, then $\{b,d\} \not\in C$.</p>

<p>I have found several references that claim or prove that every plane Eulerian graph contains a non-intersecting Eulerian circuit and at least one reference that shows how to find one in polynomial time.</p>

<blockquote>
  <p>Is there a standard reference (preferably a book on graph theory) that shows how to compute a non-intersecting Eulerian circuit in a plane Eulerian graph in polynomial time?</p>
</blockquote>

CC BY-SA 3.0
2014-05-15T22:20:53.923Z
A clarification: deciding if a planar graph has a non-intersecting Eulerian circuit (or path) is NP-complete (Bent and Manber,84).  But planar graphs with a non-intersecting Eulerian circuit is a strict subclass of  planar graphs with an Eulerian circuit so if you have a polynomial time algorithm for computing a non-intersecting Eulerian circuit in a *planar Eulerian graph* you have also a polynomial time algorithm for computing a non-intersecting Eulerian circuit in *planar graphs* (just check and discard in polynomial time graphs without an Eulerian circuit). What am I missing?
Marzio De Biasi
CC BY-SA 3.0
2014-05-15T22:55:45.500Z
@MarzioDeBiasi [Bent and Manber](http://www.sciencedirect.com/science/article/pii/0166218X8790045X) used a poor choice of words. Their "non-intersecting Eulerian circuit" is better described and known as an A-trail.  See, for example, [Andersen and Fleischner](http://www.sciencedirect.com/science/article/pii/0166218X9580001K).
Tyson Williams
CC BY-SA 3.0
2014-05-15T23:10:33.817Z
Ok, thank you! Can you give the reference, that shows how to find a non-intersecting Eulerian circuit in polynomial time (that you mentioned in the question).
Marzio De Biasi
CC BY-SA 3.0
2014-05-15T23:19:10.373Z
@MarzioDeBiasi One of the references is [Self-nonintersecting and non intersecting chains](http://link.springer.com/article/10.1007/BF01157400), which is an English translation of a Russian paper. Its algorithm works for any Eulerian graph with specified cyclic orderings at each vertex.  Plane Eulerian graphs are a special case of these.
Tyson Williams
<reference-request><graph-theory><graph-algorithms>
Standard reference for efficient computation of non-intersecting Eulerian circuit
Tyson Williams
# Standard reference for efficient computation of non-intersecting Eulerian circuit

(Asked by: username_0 on 2014-05-15)

A [plane graph](http://en.wikipedia.org/wiki/Planar_graph) $G$ defines a cyclic ordering $O(v) = \langle v\_1, v\_2, \dotsc, n\_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an [Eulerian circuit](http://en.wikipedia.org/wiki/Eulerian_path) such that for every vertex $v \in V(G)$ and every choice of four edges $\{a,v\}, \{b,v\}, \{c,v\}, \{d,v\} \in E(G)$ containing $v$, if the cyclic ordering $O(v)$ restricted to $\{a,b,c,d\}$ is $\langle a,b,c,d \rangle$ and $\{a,c\} \in C$, then $\{b,d\} \not\in C$.

I have found several references that claim or prove that every plane Eulerian graph contains a non-intersecting Eulerian circuit and at least one reference that shows how to find one in polynomial time.

> Is there a standard reference (preferably a book on graph theory) that shows how to compute a non-intersecting Eulerian circuit in a plane Eulerian graph in polynomial time?

**Tags:** reference-request, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: A clarification: deciding if a planar graph has a non-intersecting Eulerian circuit (or path) is NP-complete (Bent and Manber,84).  But planar graphs with a non-intersecting Eulerian circuit is a strict subclass of  planar graphs with an Eulerian circuit so if you have a polynomial time algorithm for computing a non-intersecting Eulerian circuit in a *planar Eulerian graph* you have also a polynomial time algorithm for computing a non-intersecting Eulerian circuit in *planar graphs* (just check and discard in polynomial time graphs without an Eulerian circuit). What am I missing?  
> **username_0**: @MarzioDeBiasi [Bent and Manber](http://www.sciencedirect.com/science/article/pii/0166218X8790045X) used a poor choice of words. Their "non-intersecting Eulerian circuit" is better described and known as an A-trail.  See, for example, [Andersen and Fleischner](http://www.sciencedirect.com/science/article/pii/0166218X9580001K).  
> **username_1**: Ok, thank you! Can you give the reference, that shows how to find a non-intersecting Eulerian circuit in polynomial time (that you mentioned in the question).  
> **username_0**: @MarzioDeBiasi One of the references is [Self-nonintersecting and non intersecting chains](http://link.springer.com/article/10.1007/BF01157400), which is an English translation of a Russian paper. Its algorithm works for any Eulerian graph with specified cyclic orderings at each vertex.  Plane Eulerian graphs are a special case of these.  

---

## 0 answers

