3
$\begingroup$

Let $G$ be an (undirected) trivalent graph. For each vertex $v$ of $G$ we choose a cyclic ordering on the edges coming into $v$ (so if vertex $A$ has neighbors $B, C$ and $D$ we decide whether the neighbors should be ordered $(B, C, D)$ or $(B, D, C)$ where $(B, C, D)$ is considered the same as $(C, D, B)$ and $(D, B, C)$ so that there are really only two choices for each vertex.

Now by a order preserving drawing of such a graph in the plane I mean a drawing where for each vector the incoming edges follow the prescribed order when reading counter clockwise. Today I made an observation that must have been known for at least 100 years:

For most choices of orderings of the edges in each vertex, in an order preserving drawing of $G$ in the plane it is necessary/inevitable that some of the edges cross, even if the underlying 'unordered' graph $G$ is planar.

For instance: for the graph of the triangular prism only 2 of the $2^6 = 64$ choices of orderings on the vertices allow a crossing free order preserving embedding into the plane, courtesy of the fact that in any such embedding of the underlying graph into the plane the choice of ordering of the edges in one vertex completely determines the ordering in the others.

So here are my questions:

1) Is there an easy way to determine the number of orderings one can put on the vertices of a trivalent graphs that allow crossing free order preserving embeddings of the graph into the plane?

2) A classical result states that a graph is planar if and only if it does not have $K_{3, 3}$ or $K_5$ as a minor. Is there a similar characterization of graphs with orderings on the edges in each vertex that can be embedded into the plane, order preserving, with no edges crossing?

$\endgroup$
0
$\begingroup$

I remembered where I have seen trivalent graphs with a cyclic ordering on the edges coming in before: long ago in the intriguing short article 'Lie algebras and the 4 color theorem' by Dror Bar-Natan. (See: https://www.math.toronto.edu/drorbn/papers/4CT/4CT.pdf.) I reread it and it contains an answer to question 1 above. (Question 2 is still open.)

Bar-Natan discusses what he calls 'a well-known construction that associates to any finite dimensional metrized Lie algebra $L$ a numerical-valued functional $W_L$ defined on the set of all oriented trivalent graphs G (that is, trivalent graphs in which every vertex is endowed with a cyclic ordering of the edges emanating from it).' Apparently, '[t]his construction underlies the gaugegroup dependence of gauge theories in general and of the Chern-Simons topological field theory in particular and plays a prominent role in the theory of finite type (Vassiliev) invariants of knots and most likely also in the theory of finite type invariants of 3-manifolds.' So, really there seems to be no upper bound on the coolness of this well known construction.

Anyway, for any Lie algebra $L$ and oriented graph $G$ we have that $W_L(G)$ is a number that depends on the orderings on the vertices but only modestly so: flipping the ordering in just one vertex multiplies the number $W_L(G)$ by $-1$.

However, the new idea of this article (or so it seems) is to compute $W_L(G)$ not just for one Lie algebra at the time, but to consider $W_L(G)$ for fixed $G$ with $L$ ranging over an entire family of Lie algebras: the $\mathfrak{sl}(N)$. The resulting function that takes the number $N$ as an input and outputs the number $W_{\mathfrak{sl}(N)}(G)$ turns out to be a polynomial with integer coefficients and Bar-Natan uses some topology to show that the degree of that polynomial is at most $v/2 + 2$ where $v$ is the number of vertices of $G$.

This prompts him to define the integer $W_{sl(N)}^{top}(G)$ as the coefficient of $N^{v/2 + 2}$ in the polynomial $W_{sl(N)}^{top}(G)$ and it is this integer that yields the answer to our question.

As far as I can see there is no faster way to compute $W_{sl(N)}^{top}(G)$ from $G$ than to compute $W_L(G)$ for at least $v/2 + 3$ different Lie algebras $L$ and if there is (these Lie algebras are not completely unrelated after all) the article does not adress it. What it does show is that the underlying unoriented graph of $G$ is planar if and only if $W_{sl(N)}^{top}(G)$ is non-zero.

Now the magic happens in the proof of this statement: on page 5 we learn that the absolute value of $W_{sl(N)}^{top}(G)$ equal the number of orderings on the vertices of the underlying graph $G$ that allow a order preserving embedding into the oriented sphere (and hence the plane), thus providing a rather unexpected answer to question 1 above.

(Remark: as can be seen in the edit history of the original post, earlier today I was rather confused about what was and wasn't going on in the Bar-Natan article. I would still be happy if someone more knowledgeable of the subject could confirm (or deny) that I got it right this time.)

| cite | improve this answer | |
$\endgroup$

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.