0
$\begingroup$

Consider the following undirected graph:

    a  
   / \  
 /     \  
b-------c  
 \     /  
  \   /  
    d

From the top-voted answer to Finding all cycles in undirected graphs I recently learned that the term Simple Cycle includes all three of the cycles in this graph: abca, bcdb, and abdca. (I originally thought Simple Cycles would only include abca and bdcb.)

Yet the Euler Equation would tell me that there are E - N + 1 = 5 - 4 + 1 = 2 cycles

Clearly these 2 cycles would be abca and bcdb.

What is the correct term for just those cycles?

$\endgroup$
7
  • $\begingroup$ Also, considering this answer (math.stackexchange.com/a/1221374/61558) and the comment under it, could there be ambiguity in this terminology? $\endgroup$
    – philologon
    Apr 10, 2017 at 23:02
  • $\begingroup$ Are you looking for the boundary cycles of the faces in the particular drawing of the graph you're looking at? Those won't be the same if you consider a different drawing of the same graph. $\endgroup$
    – hmakholm left over Monica
    Apr 10, 2017 at 23:03
  • $\begingroup$ Yes, that is what I am looking for. The only type of different drawing I can envision is one where d is moved so that edge bd crosses two other edges. Is there some other drawing (transformation) that I am not anticipating? And if so, what is the Euler Equation actually counting? $\endgroup$
    – philologon
    Apr 10, 2017 at 23:05
  • 1
    $\begingroup$ @Smylic: I think that's true for polyhedral (i.e. 3-connected) graphs, but planar graphs are a slightly larger class where the faces are not always intrinsically determined. $\endgroup$
    – hmakholm left over Monica
    Apr 10, 2017 at 23:13
  • 1
    $\begingroup$ @philologon: If you put d inside the triangle, the (inner) faces are now bcdb and abdca. $\endgroup$
    – hmakholm left over Monica
    Apr 10, 2017 at 23:18

1 Answer 1

Reset to default
2
$\begingroup$

You seem to be looking for the cycles that form the boundaries of the inner faces of the graph -- in a particular planar drawing of it.

Note that this can depend on which drawing of the graph you're looking at. For example, consider this graph:

  B------C
 / \    / \
G---A  D---H
 \ /    \ /
  F------E

Here, if I understand you correctly, one of the cycles you want to consider is ABCDEF. However if instead we draw the same graph as

  B------C
 / \    / \
G---A  H---D
 \ /    \ /
  F------E

then ABCDEF suddenly doesn't border a face (not even the outer one).

The number of faces is still the same (due to the Euler formula), but they're different ones.

$\endgroup$
3
  • $\begingroup$ Is there a concept of faces with the shortest edge distance (by edge count)? In such a case as this, that would still identify abca and bcdb, omitting abdca as I was naively thinking it ought to be anyway $\endgroup$
    – philologon
    Apr 10, 2017 at 23:29
  • 1
    $\begingroup$ @philologon: Not really -- for this particular example, ABCDEF and ABCHEF have the same length, but both cannot be faces at the same time. $\endgroup$
    – hmakholm left over Monica
    Apr 10, 2017 at 23:30
  • $\begingroup$ In my application (I think) it will not matter which Cycle wins the race to be counted as a face, but I will be favoring shorter circuits. $\endgroup$
    – philologon
    Apr 10, 2017 at 23:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .