To draw or not to draw...

Once we have a "knot shadow" notation, we must first determine whether the notation is "drawable". If not, there is no need to distinguish artificial crossings from real, or among real crossings, to distinguish overcrossings from undercrossings.

Naturally, if a notation consists of N crossings, one would expect each of the numbers 1,2,3,...,2N to appear exactly once. This however is not sufficient. One may show that in each pair, one of the numbers has to be odd, and one even. Even that is not sufficient, as we will now demonstrate with a counterexample.

Let a notation consisting of the five pairs {[1,4],[3,6],[5,8],[7,10],[9,2]}. (We pair the numbers inside brackets [], to show that the pairs are unordered, since this is a knot "shadow" and not a regular knot presentation). One may look at this figure, to realize that this notation is "undrawable" (number 8 cannot "reach" its "partner" 5 without intersecting other segments and thus violating the notation). Visually, one may always attempt to draw a notation and relatively simply determine if it can be drawn. But how can a computer program, without the benefit of "sight", respond to this challenge?

In other references in the "Knot Primer" and elsewhere, we would answer by forming all possible loops that a notation implies, and demanding that each two loops should:

a) either have one or more segments in common (in the example above, the loops 1-2-3-4 and 3-4-5-6 have the segment 3-4 in common), or

b) intersect at an even number of crossings.

If neither condition is satisfied, then the Jordan Curve Theorem would be violated if the notation were drawable. In the example above, the loops 1-2-3-4 and 5-6-7-8 intersect at only one point, [3,6], and have no segments in common. Therefore the notation is undrawable.

Due to the enormous computer time that such a check would need, we tried in the meantime to obtain alternative methods. One such method depended on the equal drawability moves. We are now going to present here another method, which we are currently using. We start with the following definition.

A crossing number is defined to be "positive", if it can "see" its partner crossing number move from left to right. If it can see its partner move from right to left, then the crossing number is "negative".

When two crossing numbers are paired to each other, one is always positive and one negative. The following question may now arise: given a particular notation, can we determine which crossing numbers are positive, and which are negative?

The answer is "yes, up to a point". Two mirror symmetric shadows have identical notations, but if the plane of symmetry is vertical, each positive crossing number is mapped to a negative and vice versa. Therefore, we can only determine the "sign" of the crossing numbers, once we arbitrarily fix one of them. The next question is "how".

The answer comes out to be the following. Let two pairs [i,j] and [k,l]. Let i be the smallest of i,j,k,l, and k less than l. If i < k < j < l, one counts the number of crossings between i and j that are paired to crossings between j and l. If this number is odd, then i and k have equal "signs", while if this number is even, then i and k have opposite signs.

In the notation of the (counter)example above, if one were to calculate the signs, one would obtain s(1) = -s(3), s(3) = -s(5), s(5) = -s(7), s(7) = -s(9), s(9) = -s(1), and thus s(1) = -s(1) which is impossible (signs can only be positive or negative, not zero). One thus demonstrates that this notation is undrawable.

But even if a notation yields consistent crossing number signs, it may still be undrawable. Take for instance the notation {[1,4],[3,8],[5,2],[7,10],[9,6]}, where one may consistently assign a positive sign to 1,3,5,7,9 and a negative sign to 2,4,6,8,10. But, as one may see by clicking here, this notation is also undrawable. One obviously wonders why, and how can one detect undrawable notations that yield consistent crossing signs. The above notation is undrawable for the following reason.

If the notation were drawable and the crossings were assigned the signs listed above, the knot shadow would separate the plane into five disjoint areas. These would be defined as follows:

Such a presentation would consist of: 5 vertices (the crossing points), 10 edges (the segments joining successive crossing points), and as shown above, 5 areas. It would thus violate Euler's theorem, which states that for a planar graph, the number of vertices plus the number of areas should be equal to the number of edges plus two. In general, any notation of N crossings defines a graph with N vertices and 2N edges. In order to fulfill Euler's theorem, the number of areas must be equal to N+2. Therefore, each notation belongs to one of the following three groups.

The first group, "led" by notation {[1,4],[3,6],[5,8],[7,10],[9,2]}, consists of notations that cannot yield consistent crossing signs. They are undrawable.

The second group, "led" by notation {[1,4],[3,8],[5,2],[7,10],[9,6]}, consists of notations that yield consistent crossing signs, but define a graph that has less than N+2 areas. Such notations are also undrawable.

The third group, "led" by notation {[1,4],[3,6],[5,2]}, consists of notations that yield consistent crossing signs and define a graph with exactly N+2 areas. These are the only drawable ones. In particular, the notation {[1,4],[3,6],[5,2]}, assigns positive signs to numbers 1,3,5 and negative signs to 2,4,6. The corresponding graph consists of the following 5 = 3 + 2 areas.

You may want to click to this page to continue with the discussion.

Charilaos Aneziris

Copyright 2001


Educational institutions are encouraged to reproduce and distribute these materials for educational use free of charge as long as credit and notification are provided. For any other purpose except educational, such as commercial etc, use of these materials is prohibited without prior written permission.