How to count the number of line segments in a knotwork?

53 Views Asked by At

Question: Given an embedded planar graph $G$, how can you compute the number of segments in the corresponding knotwork? Does the number of segments depend on choice of embedding?

Background

Any embedding of a planar graph corresponds to a particular knotwork like so; each edge corresponds to a crossing of two strands; each strand alternates crossing over and under; alternates which endpoint of the edge it is pivoting around, and alternates pivoting clockwise or anticlockwise:

a planar graph with its corresponding knotwork.

I have already worked out how to count the number of distinct strands (components $c$) of the knotwork; it's related to the Tutte polynomial of the graph via $|T_G(-1,-1)| = 2^{c-1}$ and is therefore incidentally independent of choice of graph embedding.

I am not sure how to compute the number of segments in a similar way: if we imagine knotworks drawn with unbroken lines, then topologically a knotwork is a collection of some number $k$ of line segments, whose endpoints have been glued together into groups of four ("four-way intersections"). I'm trying to find a formula for computing that number $k$ from the graph.

It seems that in simple cases, this number is equal to twice the number of edges. (four segments meet at each edge in the graph; if these were all distinct, there would be $4|E|$ strands total, but because each segment has two endpoints, we are counting each segment twice when we iterate over all the edges which serve as endpoints for these segments. Therefore there are $2|E|$ strands, as long as all of the endpoints are now distinct.)

But I am not sure whether this holds for even more complicated graphs, or how to show it. For example, graphs with leaf vertices (which cause the knotwork to have line segments whose endpoints are glued to themselves), many parallel edges, or self-loops, or some combination thereof.

1

There are 1 best solutions below

1
On BEST ANSWER

Your reasoning works no matter parallel edges and self-loops.

This is generally known in graph theory under the formula: $$\sum_{v\in V} deg(v) = 2|E|$$ This is because each edge is counted in exactly two degrees (one for each extremity). This formula is correct even when there are parallel edges and self-loops (remember that a self-loops counts for $2$ in the degree of a vertex).

Here, you can apply this argument like this: You have one intersection for each edge, so the graph formed by your segments has $|E|$ vertices, and it is four regular (4 segments are incident at each vertex). So you have $\frac{4|E|}{2} = 2|E|$ segments.