What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)? For instance, the digraph (given by an NFA; ignore edge labels please) below becomes a tree $\{a,b,c,d\}$ with edges $(a,b), (b,c), (b,d)$ via: \begin{eqnarray*} a\mapsto&\text{the cycle }&S_0,S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_0 \\ b\mapsto &\text{the cycle }&S_5,S_6,S_7,S_8,S_9,S_{10},S_{11},S_{12},S_5\\ c\mapsto &\text{the cycle }&S_8,S_9,S_8\\ d\mapsto &\text{the cycle }&S_{10},S_{11},S_{12},S_{10} \end{eqnarray*} Complexity witness

  • 1
    $\begingroup$ How are you collapsing loops? Every acyclic connected graph is a tree, so if your collapsing doesn't disconnect the graph you'll always end up with a tree. $\endgroup$ Nov 26, 2018 at 17:21
  • 1
    $\begingroup$ I edited your question to replace "loops" with "cycles": a loop is an edge from a vertex to itself. But I can't tell what you're asking, here. First, what do you mean by "collapsing"? Second, what do you mean by "a tree like $\{0,00,000,001\}$? Third, are these graphs or automata? Those aren't the same thing but you talk about them as if they are. $\endgroup$ Nov 26, 2018 at 17:58
  • $\begingroup$ @DavidRicherby thanks for the point about cycles vs. loops. I've edited to clarify the rest. $\endgroup$ Nov 26, 2018 at 18:31
  • $\begingroup$ OK but you need to give a definition, not just an example. Actually, I don't understand your example at all. Going round the cycle $S_{10}S_{11}S_{12}S_{10}$ generates the string $110$, not $01$; So where do these strings come from? $\endgroup$ Nov 26, 2018 at 18:34
  • $\begingroup$ my guess it that these graphs are the series parallel graphs, or equivalently graphs that are K4-minor-free $\endgroup$ Nov 27, 2018 at 3:20

1 Answer 1


For any given undirected graph $G$, the cycle graph $C(G)$ has vertices which correspond to the chordless cycles of $G$, and two distinct vertices of $C(G)$ are adjacent if and only if the corresponding chordless cycles have at least one edge in common. [1]

Judging from your example, you are interested in a similar notion for a directed graph.

[1] S.V. Gervacio. Cycle graphs. Lect. Notes Math. 1073, 279-293 (1984)

  • $\begingroup$ Thanks, I wonder whether chordless cycles is the right concept though, since the cycle $b$ in my example is apparently not chordless $\endgroup$ Dec 11, 2018 at 1:49
  • $\begingroup$ A face-defining cycle is chordless. $\endgroup$
    – Vincenzo
    Dec 11, 2018 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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