0
$\begingroup$

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)

Improve this question
$\endgroup$
1
  • $\begingroup$ The paper mentioned in the post has various editions. However, not all of them contain the "extracting elementary cycles" part in Section 4. So I have added a link to an edition which does contain it. $\endgroup$ – hengxin Jan 10 '15 at 5:58
0
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Will accounting for those two cases produce the path-set P? Assume a graph with 3 black and 3 white vertices, having edges B1-W1, W1-B2, B2-W2, W2-B1 (cycle 1), W1-B3, B3-W2 (cycle 2 along with B1 or B2) and a dead end B3-W3. If cycle 1 is selected initially, no more tours will be joined to it. But $H$ - $C$ is a tree rather than a path. $\endgroup$ – Aeris130 Jan 10 '15 at 6:48
  • $\begingroup$ @Aeris130 The tree can be decomposed into two paths, for example, $W_1 \to B_3 \to W_3$ and $W_2 \to B_3$ which have disjoint begin- and endpoints. Is this allowed for the following processing? $\endgroup$ – hengxin Jan 10 '15 at 7:17
  • $\begingroup$ @Aeris130 Are there any other constraints on the graph $H$? In the same paragraph, I find that Recall that H is bipartite, and all white vertices have degree 2 (however, Figure 7(a) does not agree with this). $\endgroup$ – hengxin Jan 10 '15 at 7:24
  • $\begingroup$ The text mentions degree 2 for white vertices after discussing how to add edges from the cycle/paths to the final graph, so I assume it refers to the cycle and internal path vertices and not $H$ (since all three figures in the article contradicts this). As for decomposing trees into paths, nothing is said about it. Only that $H$ - $C$ = $P$. $\endgroup$ – Aeris130 Jan 10 '15 at 7:32
  • $\begingroup$ @Aeris130 Also in the same paragraph: Call vertices $v''$ representing the 2-subgraphs $V''$ black and the other vertices of $H$ white. This may pose degree constraints on black vertices. For example (just a guess), all black vertices have even degrees. If this is true, your example graph is not a counterexample. $\endgroup$ – hengxin Jan 10 '15 at 7:47

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.