[Solved]: Finding undirected cycles in linear time (triangulating graphs while minimizing degree)

Problem Detail: 

In the article ["Triangulating Planar Graphs While Minimizing the Maximum Degree"] by Kant and Bodlaender [1], Section 4 briefly mentions the extraction of elementary cycles (no repeating edges) from what I assume is an undirected graph $H$. It has the following to say:

$H$ is planar and bipartite.

...using a simple modification of Euler's technique to find an Eulerian cycle in a graph, we can extract the elementary cycles $C_\mathrm{elem}$ from $H$.

Thus $H - C_\mathrm{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

In the proof section it mentions that extracting elementary cycles and disjoint paths can be executed in linear time, allowing the triangulation algorithm as a whole to do the same.

From what I understand, there are no algorithms that compute the simple cycles of an undirected graph in linear time, raising the following questions:

• Which algorithm does "Euler's technique to find an Eulerian cycle" refer to? There seem to be several algorithms with varying performance.
• What is the "simple modification" in question? The paper doesn't say, and I haven't been able to find anything on the net.

---

[1] G. Kant and H. Bodlaender, "Triangulating Planar Graphs While Minimizing the Maximum Degree". Information and Computation, 135:1(1–14), 1997. (Science Direct)

Asked By : Aeris130

Answered By : hengxin

Which algorithm does "Eulers technique to find an Eulerian cycle" refer to?

It probably refers to the Hierholzer algorithm (wiki) which takes linear time.

The algorithm below is from the wiki article.

1. Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$.
   It is not possible to get stuck at any vertex other than $v$, because the even degree of all vertices ensures that, when the trail enters another vertex $w$ there must be an unused edge leaving $w$.
   The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.

2. As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and join the tour formed in this way to the previous tour.

What is the "simple modification" in question?

Hierholzer algorithm aims to apply to Eulerian graphs which are (and should be) graphs with every vertex of even degree. In your problem, $H$ is not necessarily an Eulerian graph.

So it needs modifications: In step 1, the closed tour from $v$ to $v$ may not exist at all; and in step 2, you may not be able to start another trail from $u$, or you may not be able to return to $u$.

Thus $H−C_{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

This can be seen from Figure 7(b) in the paper.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/37106