1
$\begingroup$

Let $\{C(G)\}$ be the set of chordless cycles of a graph $G$. Compare the cycles pairwise. Let $\{V\}$ represent the pairs which have exactly one vertex in common; and, let $\{P\}$ represent those pairs which have a single continuous sequence of edges, ie, a path, in common. For a pair in $\{V\}$, let $X$ denote their common vertex. Obviously, for planarity, the edges at vertex $X$ must be ordered so that the cycles do not overlap, ie., crossover. Similar restrictions obtain on the orderings at the two terminal vertices for the common path shared by a pair of cycles in $\{P\}$.

In either type of conjunction, certain edge orderings on common vertices are required for planarity of $G$. Have the Kuratowski criteria for planarity been shown to be equivalent to the two types of restrictions described above?

Improve this question
$\endgroup$
2
  • $\begingroup$ 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} ? $\endgroup$
    – JimN
    Commented Sep 16, 2020 at 23:42
  • $\begingroup$ 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. $\endgroup$
    – Jim farned
    Commented Sep 17, 2020 at 21:13

1 Answer 1

Reset to default
1
$\begingroup$

I believe there is a characterization like the one you mention.

The de Fraysseix–Rosenstiehl planarity criterion traverses a given graph with a depth-first search and characterizes the way edges can exist in this ordering with respect to being on certain sides of other visited paths.

It is not immediately clear whether your conditions would be exactly like these ordered-edge conditions, but the fact that there is a characterization that uses edge orderings suggests that you might be able to formalize yours into something similar or equivalent.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks again for a good lead! I am currently studying the possibility you suggest. $\endgroup$
    – Jim farned
    Commented Sep 18, 2020 at 20:45

You must log in to answer this question.

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