Timeline for Chordless cycles and planarity in graphs
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 18, 2020 at 6:04 | answer | added | JimN | timeline score: 1 | |
| Sep 17, 2020 at 21:13 | comment | added | Jim farned | My sense is that if the graph is simplified (eg., vertices with only two edges intersecting are eliminated), then the usual definition of "chordless cycle" would suffice. Here is my intuition. Suppose there are two chordless cycles, X and Y. X={ab,bc,cd,de,ea} and Y={pq,qr,rc,ct,tp}. Then at the common vertex c, four edges must be properly ordered (say, clockwise) around the vertex c. Obviously, the ordering (bc)(rc)(cd)(ct) would violate planarity, as the chordless cycles would overlap. | |
| Sep 16, 2020 at 23:42 | comment | added | JimN | can you elaborate on 'chordless cycles' ? Most definitions refer to a chord of a cycle $v_1,v_2,v_3,v_4,...,v_n,v_1$ to mean an edge from one $v_i$ to another $v_j$ with $|i-j| \neq 1$ (mod n). But I think in your context, you would be counting a path to qualify as a chord. Does the path necessarily have to be a subdivision of a single edge? Can you maybe illustrate your V and P for a graph like {ab,bc,cd,de,ef,fa, gf,gb,he,hc} ? | |
| Sep 16, 2020 at 21:41 | history | edited | YCor | CC BY-SA 4.0 |
formatting, added tag
|
| Sep 16, 2020 at 21:07 | history | edited | Jim farned | CC BY-SA 4.0 |
added 340 characters in body
|
| Sep 16, 2020 at 21:01 | review | First posts | |||
| Sep 16, 2020 at 23:13 | |||||
| Sep 16, 2020 at 20:58 | history | asked | Jim farned | CC BY-SA 4.0 |