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)