\datethis \input epsf \let\possiblyflakyepsfbox=\epsfbox \def\epsfbox#1{\hbox{\possiblyflakyepsfbox{#1}}} \def\adj{\mathrel{\!\mathrel-\mkern-8mu\mathrel-\mkern-8mu\mathrel-\!}} % adjacent vertices \def\dadj{\mathrel{\!\mathrel-\mkern-8mu\mathrel-\mkern-12mu\to\!}} \everypar{\looseness=-1} @s step int @*Introduction. This program does calculations with skew ternary trees, and exhibits the corresponding nonseparable planar graphs. It implements some simple algorithms that I discovered in November, 2013, based on ideas of Alberto Del Lungo, Francesco Del Ristoro, and Jean-Guy Penaud [{\sl Theoretical Computer Science\/ \bf233} (2000), 201--215]. I wrote it in order to learn more about the seemingly magical properties of this amazing correspondence. I apologize for having no time to provide a better user interface, or to give more extensive commentary. Ideally an interactive system should be written, with excellent graphics to display and manipulate the trees and graphs in an intuitive fashion; color should be used to exhibit at least some of the fascinating patterns that are present, etc. I'm hoping that some reader will be motivated to write such an app,'' because it will certainly be a fabulously instructive toy. I will at least try to define and explain the basics in this document. A ternary tree is either empty, or it consists of a root node and three ternary trees called the left, middle, and right subtrees of the root. The roots of those subtrees are called the left, middle, and right children of the root node. (This definition is strictly analogous to the familiar definition of binary trees, in Section 2.3 of my book {\sl Fundamental Algorithms}.) Furthermore we extend the ternary tree by placing buds'' in the positions of empty subtrees. And we also introduce a bud at the top, attached to the root node. In this way every node, including the root, is attached to exactly four other nodes or buds; and every bud is attached to exactly one other node or bud. We will give labels to each node and to each bud, in order to exhibit fine details of the structure. An extended ternary tree with $n$ nodes always has $2n+2$ buds. (Notice that this result, which is easily proved by induction on~$n$, holds in particular when the ternary tree is empty. In that case, $n=0$ and there simply are two buds joined to each other.) The embedding of such a tree in the plane leads to a family of $2n+2$ extended ternary trees that are cyclically equivalent,'' as illustrated below. There's one such tree for each bud, obtained by placing that bud at the top and letting everything else hang down'' from it in. Each of these trees has a different root bud, but not necessarily a different root, because different buds can lead to distinct trees with the same root node. The $2n+2$ buds can always be paired up into $n+1$ groups of two. Indeed, we can find the mate of any bud by proceeding on a unique path away from that bud, always taking the middle branch whenever there are three choices for the next step, and continuing until another bud is encountered. Every node and every bud is assigned a {\it rank\/} in the following natural way: The root node and root bud have rank zero; and the left, middle, and right children of a rank~$r$ node have ranks $r-1$, $r$, and $r+1$, respectively. A {\it skew ternary tree\/} is a ternary tree for which all nodes have nonnegative rank. For example, the skew ternary tree shown here has 6 nodes and 7 pairs of buds. Ranks are shown in red. Notice that there's one bud of rank $-1$ for every node of rank~0. $$\vcenter{\epsfbox{skew-ternary-calc.1}}\qquad\qquad \vcenter{\epsfbox{skew-ternary-calc.3}}$$ @ Fact: {\sl Every family of $2n+2$ cyclically equivalent ternary trees includes exactly four skew ternary trees.} Moreover, this theorem---which is the main reason for the existence of this program---has an astonishingly simple proof. The idea is to consider the $n-1$ edges that go between nodes of the ternary, and to treat each edge $\.U \adj \.V$ as a pair of arcs $\.U \dadj \.V$ and $\.V \dadj \.U$. That gives us $2n-2$ arcs. And there's a natural way to match those arcs to $2n-2$ of the $2n+2$ buds, by means of $2n-2$ noncrossing filaments as illustrated here: $$\vcenter{\epsfbox{skew-ternary-calc.2}}$$ More precisely, imagine an ant, named Alice, who crawls around the periphery of the tree. Alice starts in state $-2$, just to the right of bud number~0. She increases her state by~1 whenever she passes a bud; and she decreases her state by~1 whenever she passes an arc. Then she will be in state $-2+(2n+2)-(2n-2)=+2$ when she returns to its starting point: $$\vcenter{\epsfbox{skew-ternary-calc.4}}$$ And if she keeps on crawling, she will repeat the same pattern, but with her state increased by~4. The key fact is that Alice is in state $k$ whenever she reaches a bud of rank~$k$---except for the starting bud, when she's in state $\pm2$. Thus the unmatched buds correspond to the skew ternary trees; in this example the trees whose roots hang down from buds 0, 4, 5, and 6 will have no nodes of negative rank. Conversely, a ternary tree that begins at a matched bud will have at least one buds of rank $<-1$, so it will have at least one node of rank $<0$. {\mc QED}. \smallskip (A reader who understands this proof will also be able to show that {\sl every family of $4n+2$ cyclically equivalent {\it quinary trees\/} includes exactly six skew quinary trees.} And so on.) @ The four skew ternary trees of a cyclic family turn out to have remarkable properties. Let's look at the state transitions that Alice would encounter by starting at each of the four unmatched buds: \vcenter{\halign{#\hfil\cr \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.5}\cr\noalign{\smallskip} \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.6}\cr\noalign{\smallskip} \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.7}\cr\noalign{\smallskip} \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.8}\cr}} The corresponding skew ternary trees, which we might as well show without their buds, are $$T=\vcenter{\epsfbox{skew-ternary-calc.10}}\;;\qquad T^+=\vcenter{\epsfbox{skew-ternary-calc.11}}\;;\qquad T^{++}=\vcenter{\epsfbox{skew-ternary-calc.12}}\;;\qquad T^{+++}=\vcenter{\epsfbox{skew-ternary-calc.13}}\;.$$ Notice the notation used here, based on a well-defined operator $T\mapsto T^+$ that takes one skew ternary tree to another. Since $T^{++++}=T$, we also abbreviate $T^{+++}$ as $T^-$; and $T^{++}$ can also be called $T^{--}$. @ One of the first goals of this program will be to compute the conjugates'' $T^+$, $T^{++}$, and $T^{+++}=T^-$, given a skew ternary tree~$T$. That tree is specified on the command line, as a sequence of four-character arguments \.{abcd}: The first character, \.a, names a node; the next three characters name that node's children, using \.-' for an empty child. For example, the tree $T$ above could be specified by the six command-line arguments $$\.{A-BD} \qquad \.{B--C} \qquad \.{C---} \qquad \.{DE-F} \qquad \.{E---} \qquad \.{F---}$$ in some order. There should be one argument for each node. The program parses the arguments and checks to make sure that they actually do define a skew ternary tree. @ OK, we now know the definition of skew ternary trees, and it's time to begin coding. Here's the structure of the program as a whole: @c #include #include #include @@; @@; @@; @@; main (int argc, char *argv[]) { register int c,i,j,k,p; @; @; @; } @ We don't deal with the empty tree; there must be at least one node. @= if (argc==1) { fprintf(stderr,"Usage: %s node_1 node_2 ... node_n\n",argv[0]); exit(-1); } @; @* Parsing. First things first: We gotta get the tree into memory in a convenient form. The basic data structure has |left|, |middle|, |right|, and |parent| fields in each node, and a few other things we'll need as we go along. Buds are represented by negative integers; other links are to a node's 8-bit character code. (At most 64 different visible character codes are used in this implementation, namely |'*'| and the 63 from |'@@'| to |'~'|.) @d sentinel 999 @d maxcodes 64 @= typedef struct node_struct { int left; /* the left child */ int middle; /* the middle child */ int right; /* the right child */ int parent; /* the parent */ int rank; /* set to |sentinel| at input time; later is the actual rank */ } node; @# typedef struct bud_struct { int parent; /* the parent */ int rank; /* the actual rank */ int stepno; /* step number in the state chart (see below) */ } bud; @ @= node inputnode[256]; /* actually only nodes |'@@'| thru |'~'| are used */ bud inputbud[512]; /* data for bud number |k| is stored in |inputbud[-k]| */ int buds; /* this many buds have been created so far */ int n; /* the number of nodes in the tree */ @ The initial setup is straightforward, although a bit tedious. @d abort0(message,code) {@+fprintf(stderr,"%s!\n", message); exit(code);@+} @d abort1(message,j,code) {@+fprintf(stderr,"Bad arg (%s): %s!\n", argv[j],message); exit(code);@+} @d abort2(message,j,c,code) {@+fprintf(stderr,"Bad arg (%s): Node '%c' %s!\n", argv[j],c,message); exit(code);@+} @= for (j=1;j'~') abort2("is not permitted",j,c,-15); if (inputnode[c].rank) abort2("has already been defined",j,c,-11); inputnode[c].rank=sentinel; p=argv[j][1]; if (p!='-') { if (p<'@@' || p>'~') abort2("is not permitted",j,p,-16); if (inputnode[p].parent) abort2("already has a parent",j,p,-12); inputnode[c].left=p,inputnode[p].parent=c; } p=argv[j][2]; if (p!='-') { if (p<'@@' || p>'~') abort2("is not permitted",j,p,-17); if (inputnode[p].parent) abort2("already has a parent",j,p,-13); inputnode[c].middle=p,inputnode[p].parent=c; } p=argv[j][3]; if (p!='-') { if (p<'@@' || p>'~') abort2("is not permitted",j,p,-18); if (inputnode[p].parent) abort2("already has a parent",j,p,-14); inputnode[c].right=p,inputnode[p].parent=c; } } n=argc-1; @; @ We need to locate the root, which should be the unique input node that has no parent. Then we'll attach bud |-1| to it. Buds $-2k-1$ and $-2k-2$ are mates; hence the mate of bud |x| is bud |x^1|. @d root inputbud[1].parent @= for (j='@@';j<='~';j++) { if (inputnode[j].rank && !inputnode[j].parent) { if (root) { fprintf(stderr,"Nodes '%c' and '%c' cannot both be roots!\n", root,j); exit(-20); } root=j; } if (inputnode[j].parent && !inputnode[j].rank) { fprintf(stderr,"No data was supplied for node %c'!\n", j); exit(-21); } } if (!root) abort0("There's no root",-21); inputbud[1].rank=-2; /* bud number 1 is the root bud,'' above the root node */ setmate(root); /* locate and define its mate */ fillbuds(root,0); @; @ The |setmate| subroutine allocates two new buds. Its parameter names the node where we discovered the existence of such buds. In most cases, the mate is reached by going upward through middle links, then crossing from left to right (or vice versa) and going downward through middle links. @= void setmate(int p) { register int q,d; buds+=2, q=1-buds; if (inputbud[buds-1].parent) { if (buds>2) confusion("bud parent already set"); goto downward_mid; } inputbud[buds-1].parent=p; upward:@+if (inputnode[p].middle==q) { q=p,p=inputnode[p].parent; goto upward; } if (inputnode[p].left==q) { q=p,p=inputnode[p].right,d=1; goto downward; } if (inputnode[p].right==q) { q=p,p=inputnode[p].left,d=-1; goto downward; } confusion("supposed parent node not apparent"); downward_mid: q=p,p=inputnode[p].middle,d=0; downward:@+if (p<0) abort0("Mate mixup",-25); if (p>0) goto downward_mid; if (d>0) inputnode[q].right=-buds; else if (d<0) inputnode[q].left=-buds; else inputnode[q].middle=-buds; inputbud[buds].parent=q; } @ The main work of filling buds and setting ranks is done by a straightforward recursive procedure |fillbuds|, which traverses the ternary tree in preorder. @= void fillbuds(int p,int r) { if (r<0) { fprintf(stderr,"Not properly skewed: rank(%c)=-1!\n",p); exit(-30); } inputnode[p].rank=r; if (inputnode[p].left>0) fillbuds(inputnode[p].left,r-1); else { if (inputnode[p].left==0) inputnode[p].left=-buds-1,setmate(p); inputbud[-inputnode[p].left].rank=r-1; } if (inputnode[p].middle>0) fillbuds(inputnode[p].middle,r); else { if (inputnode[p].middle==0) inputnode[p].middle=-buds-1,setmate(p); inputbud[-inputnode[p].middle].rank=r; } if (inputnode[p].right>0) fillbuds(inputnode[p].right,r+1); else { if (inputnode[p].right==0) inputnode[p].right=-buds-1,setmate(p); inputbud[-inputnode[p].right].rank=r+1; } } @ We've prepared a skewed ternary tree by filling in all the missing fields. But if the input is, say, \.{A---} \.{B-B-}', the tree we've prepared won't contain all of the given nodes, because of a cycle. Thus we must make sure that the number of buds found is $2n+2$. @= if (buds!=n+n+2) abort0("The input contains a cycle",-66); @*The state chart. Now that we've got the tree in memory, we can emulate Alice's moves. This program gathers more information than is absolutely needed, just in case the extra data will help me psych out some structural properties. @= typedef struct step_struct { int rank; /* rank on entry */ int first; /* bud being passed, or arc's initial node */ int second; /* arc's final node (in the second case) */ int match; /* bud being matched (in the second case) */ } step; @ @= step chart[4*maxcodes]; /* the state chart, of length $4n$ */ int steps; /* the current number of entries in |chart| */ int stack[256]; /* buds currently unmatched */ int stacked; /* the number of such buds */ @ @= @; @; @; @ The state chart is created from a recursive routine |createsteps|, analogous to |fillbuds|. @= void branch(int,int); /* see below */ void budstep(int); /* see below */ void createsteps(int p) { register int q; q=inputnode[p].left; if (q>0) branch(p,q); else budstep(-q); q=inputnode[p].middle; if (q>0) branch(p,q); else budstep(-q); q=inputnode[p].right; if (q>0) branch(p,q); else budstep(-q); } @ @d offset 2 /* difference between |stacked| and the current rank */ @= void budstep(int b) { /* chart gains a bud */ chart[steps].first=b,chart[steps].rank=stacked-offset; if (chart[steps].rank!=inputbud[b].rank) confusion("rank offense b"); inputbud[b].stepno=steps; steps++,stack[stacked++]=b; } @ @= void branch(int p,int q) { /* chart passes from one arc to its dual */ chart[steps].first=p,chart[steps].second=q,chart[steps].rank=stacked-offset; if (chart[steps].rank!=inputnode[q].rank) confusion("rank offense q"); chart[steps].match=stack[--stacked]; steps++; createsteps(q); chart[steps].first=q,chart[steps].second=p,chart[steps].rank=stacked-offset; if (chart[steps].rank!=inputnode[q].rank+2) confusion("rank offense p"); chart[steps].match=stack[--stacked]; steps++; } @ @= chart[0].rank=-2, chart[0].first=1, steps=1; stack[0]=1, stacked=offset-1; createsteps(root); if (stacked!=2+offset) confusion("mismatched"); if (steps!=4*n) confusion("total steps"); @ Conversely, given the state chart, there's a simple recursive routine that prints a tree beginning after an unmatched bud. Interestingly, the nodes of the tree are reported in postorder although they are encountered in preorder. @= void printfam(int p) { register int q; int l,m,r; if (steps==4*n) steps=0; q=chart[steps++].second; if (q==0) l='-'; else l=q,printfam(q),steps++; if (steps==4*n) steps=0; q=chart[steps++].second; if (q==0) m='-'; else m=q,printfam(q),steps++; if (steps==4*n) steps=0; q=chart[steps++].second; if (q==0) r='-'; else r=q,printfam(q),steps++; printf(" %c%c%c%c", p,l,m,r); } @ The algorithm here is very cute, so I let the reader have the fun of deciphering it. @= chart[4*n].second=sentinel,chart[4*n].first=root; for (j=1;j<4;j++) { for (i=0;i= print_tree(root); printf("\n"); @ @= void print_tree(int p) { /* prints node |p|'s subtree in preorder */ register int i; for (i=0;i0) print_tree(inputnode[p].left); if (inputnode[p].middle>0) print_tree(inputnode[p].middle); if (inputnode[p].right>0) print_tree(inputnode[p].right); } @*The quad-edge data structure for planar maps. Turning from trees to more complex graphs drawn in the plane, we now implement some beautiful data structures that were introduced by Leo Guibas and Jorge Stolfi in {\sl ACM Transactions on Graphics\/ \bf4} (1985), 74--123. The best way to understand their quad-edge structure'' is to consider a small example. The normal way to draw a planar graph with, say, vertices $\{1,2,3,4\}$ and edges $\{a,b,c,d,e,f\}$ and faces $\rm\{I,II,III,IV\}$ is to connect the vertices by lines for the edges, and to name the faces in the enclosed regions: $$\vcenter{\epsfbox{skew-ternary-calc.21}}\eqno({*})$$ Inside a computer, however, the best way to represent the topology of this diagram is to construct a more elaborate structure, which can be regarded as annotating the graph~$(*)$ and embedding it in a richer graph: $$\vcenter{\epsfbox{skew-ternary-calc.20}}\eqno({**})$$ Vertices (red) and faces (green) have been replaced by oriented cycles, which all travel counterclockwise, except that the outermost cycle runs clockwise. (That cycle would run the other way if we drew it on the equator of a sphere and looked at it from the south pole, while viewing the rest of the map from the north pole.) The oriented cycles in $(**)$ have little connectors that we shall call pips.'' The cycle for a vertex $v$ of degree~$d$ has $d$ pips, which indicate all of the edges adjacent to~$v$, in counterclockwise order. Similarly, the cycle for a face indicates all of the edges surrounding that face, as we march counterclockwise around it. One advantage of a representation like $(**)$ is the fact that it nicely represents also the {\it dual\/} graph, in which vertices become faces, faces become vertices, and edges rotate'' by $90^\circ$. For example, the dual of $(*)$ is the planar graph $$\vcenter{\epsfbox{skew-ternary-calc.22}}\,.\eqno({*{*}*})$$ @ Notice that each of the edges $\{a,b,c,d,e,f\}$ in $(*)$ appears as a vertex in~$(**)$. Every such vertex has degree~4, and it connects to four pips via lines numbered 0, 1, 2, and~3 in clockwise order. The pips on lines 0 and 2 always belong to vertex cycles; the pips on lines 1 and 3 always belong to face cycles. We could change the numbers $(0,1,2,3)$ to $(2,3,0,1)$, respectively, at each edge-vertex, without changing the meaning of this diagram; the actual numbering of these lines isn't important. But their cyclic ordering is crucial, and so is their evenness or oddness. I should point out that two planar graphs are considered to be essentially the same if they are topologically equivalent when drawn on the surface of a sphere. They should represent the same decomposition of the sphere's surface into regions delimited by the given edges, in the sense that we could transform one drawing into the other, smoothly and without trickery. In particular, we could redraw $(*)$ in three equivalent ways by choosing any of the other faces to be exterior: $$\def\epsfsize#1#2{.8#1} \vcenter{\epsfbox{skew-ternary-calc.23}}\qquad \vcenter{\epsfbox{skew-ternary-calc.24}}\qquad \vcenter{\epsfbox{skew-ternary-calc.25}}$$ Each of these graphs corresponds precisely to the vertices, edges, faces, and pips of~$(**)$; and so are three variants of~$(*{*})$! Butleft-right reflection would give a different graph in this case, because $(*)$ has no symmetry. @ Suppose there are $m$ edges. Diagram $(**)$ can also be regarded as a {\it permutation\/} of the $4m$ pips, expressed in cycle form, namely $$\alpha=(a_2d_2c_2b_2)(d_0e_2)(c_0e_0f_0)(a_0b_0f_2) (a_1f_1e_3d_3)(c_3d_1e_1)(b_3c_1f_3)(a_3b_1).$$ These cycles correspond to vertices (1), (2), (3), (4) and faces (I), (II), (III), (IV); for instance, $(a_0b_0f_2)$' describes the cycle $a_0\dadj b_0\dadj f_2\dadj a_0$ for vertex~4 in~$(**)$. Guibas and Stolfi noted that the permutations $\alpha$ obtained from planar maps in this way have a very important property called the backup axiom: {\sl If $\alpha$ takes $u_{i+1}\mapsto v_j$}, where $u$ and~$v$ are edges of the planar graph being represented and where their subscripts are treated modulo~4, {\sl then $\alpha$ also takes $v_{j+1}\mapsto u_i$}. For example, $a_2\mapsto d_2$ and $d_3\mapsto a_1$ in $\alpha$. Notice that $a_2$ and $d_2$ are vertex pips, but $d_3$ and $a_1$ are face pips. The backup axiom can be formulated in terms of permutations, using the special rotation'' permutation $$\rho=(a_0a_1a_2a_3)(b_0b_1b_2b_3)(c_0c_1c_2c_3)(d_0d_1d_2d_3) (e_0e_1e_2e_3)(f_0f_1f_2f_3);$$ namely, it is equivalent to saying that $\alpha\rho\alpha\rho$ is the identity permutation. After moving from any pip by applying $\alpha$ and then $\rho$, we can back up to our original state by applying $\alpha$ and~$\rho$ again. This principle underlies the efficiency of a quad-edge structure, because we can easily move in the clockwise or counterclockwise direction around any vertex or around any face; we needn't traverse the whole cycle to find our predecessor. Continuing our example, we have $$\alpha\rho= (a_0b_1)(a_1f_2)(a_2d_3)(a_3b_2)(b_0f_3)(b_3c_2) (c_0e_1)(c_1f_0)(c_3d_2)(d_0e_3)(d_1e_2)(e_0f_1).$$ In general $\alpha\rho$ will always be a permutation of order~2, which takes every vertex pip into some face pip. Therefore $\alpha\rho$ consists entirely of two-cycles; it's a matching between the $2m$ vertex pips and the $2m$ face pips. Similarly, $\rho\alpha$ always consists of two-cycles; in our case it's $$\rho\alpha= (a_0f_1)(a_1d_2)(a_2b_1)(a_3b_0)(b_3f_2)(b_2c_1) (c_3e_0)(c_0f_3)(c_2d_1)(d_3e_2)(d_0e_1)(e_3f_0).$$ We'll have $(u_iv_j)$ in $\rho\alpha$ if and only if $(u_{i+1}v_{j+1})$ is in $\alpha\rho$, because of the backup axiom. For example, $\rho\alpha$ contains $(a_1d_2)$ which $\alpha\rho$ contains $(a_2d_3)$. The regions outside the cycles in $(**)$ all have four sides. For example, there's a region near the top right whose corner pips in counterclockwise order are $(d_3,d_2,a_2,a_1)$. The backup axiom explains this fact. Moreover, it tells us that the pips at opposite corners, such as $\{d_3,a_2\}$ and $\{d_2,a_1\}$, are the pips matched by $\alpha\rho$ and $\rho\alpha$. @ Thus the quad-edge data structure for a planar graph with $m$ edges essentially consists of $4m$ pointers, which tell us how to move from one pip to another. These pointers form a permutation of the pips, where the permutation takes vertex pips into vertex pips and face pips into face pips. It also satisfies the backup axiom. Guibas and Stolfi also observed that every planar graph without isolated vertices can be constructed by repeatedly performing a single primitive operation. This operation, called {\it splice}, exchanges two vertex pips and two face pips. (Well, there's also a primitive operation that initializes the entire data structure. To get things rolling, we begin with a set of $m$ edges that define $m$ two-vertex components; thus we have $2m$ vertices initially, each of degree~1. After the initialization, we can proceed to splice until we've got the graph we want.) The best way to understand splicing is---guess what---to look at a small example. So let's construct the pip-permutation~$\alpha$ above, and the planar graph above, by a sequence of splices. We begin with the initial permutation $$\alpha_0\beta_0\gamma_0\delta_0\varepsilon_0\varphi_0;$$ here $\alpha_0=(a_0)(a_2)(a_1a_3)$, $\beta_0=(b_0)(b_2)(b_1b_3)$, \dots, and $\varphi_0=(f_0)(f_2)(f_1f_3)$ each specify a two-vertex graphs~$K_2$ disjoint from the others. The sub-permutation $\alpha_0$ corresponds to the two-vertex graph whose edge is named~$a$, and the other sub-permutations are similar. Two edges $a$ and $b$ belong to the same component of a graph if and only if there's a sequence $(d_1,d_2,\ldots,d_r)$, for some~$r$, such that $\alpha\rho^{d_1}\alpha\rho^{d_2}\ldots\alpha\rho^{d_r}$ takes $a_0\mapsto b_0$. If the graph has $c$ components, we can best think of it as a set of $c$ connected graphs, each of which is drawn on the surface of a separate sphere; thus each component has its own exterior face.'' According to a famous theorem of Euler, the number of vertices plus the number of faces is always equal to the number of edges plus $2c$. A splice $\sigma$ consists of applying two swap operations; in other words, $\sigma$ has the form $(u_iv_j)(r_ks_l)$. Here $i$ and $j$ are even (hence $u_i$ and $v_j$ are vertex pips), while $k$ and $l$ are odd (hence $r_k$ and $s_l$ are face pips). If $u_i$ and $v_j$ lie in different cycles of~$\alpha$, then they lie in the same cycle of $\alpha\sigma$; in fact, they are obtained by pasting the cycles together in a straightforward way: $$(u_ix_1\ldots x_p)(v_jy_1\ldots y_q)(u_iv_j) =(u_ix_1\ldots x_pv_jy_1\ldots y_q).$$ For example, if $u$ and $v$ are edges of different components, it's clear that $u_i$ and $v_j$ must lie in different cycles; and in that case the net effect is to paste two disconnected components of a graph together, with two vertices coalescing into one. If $u$ and $v$ are edges of the same component, but $u_i$ and $v_j$ aren't in the same cycle, then we're allowed to splice them together only if $u_{i+1}$ and $v_{j+1}$ are pips of the same face. Otherwise we couldn't merge the vertices of $u_i$ and $v_j$ without making lines cross. (That's a consequence of Euler's theorem, mentioned above; we'd be drawing the component on a torus, not a sphere.) Going the other way, suppose $u_i$ and $v_j$ do lie in the same cycle of~$\alpha$. Then the splice operation splits the graph into two parts, making two copies of the vertex whose pips included $u_i$ and $v_j$; one copy gets some of the adjacent edges, the other copy gets the rest. Actually, however, we won't need to do splices of this kind; it's possible to form any desired planar graph without isolated vertices merely by pasting vertices together, decreasing the number of vertices with each splice. Similar remarks apply to the cycles of face pips, depending on whether or not $r_k$ and $s_l$ belong to the same cycle of~$\alpha$. A swap operation between elements of different cycles always merges the cycles; a swap operation between elements of a single cycle always splits that cycle. The value of $(r_ks_l)$ is completely determined by the value of $(u_iv_j)$ by the following important {\it splice rule\/}: If~$\alpha$ takes $u_{i+1}\mapsto x_p$ and $v_{j+1}\mapsto y_q$, then $r_k=x_p$ and $s_l=y_q$. This rule is necessary so that the backup axiom is preserved; we can't paste vertices together or split them apart unless we do an exactly consistent thing with respect to the faces. And fortunately, the splice rule is also sufficient for maintaining the backup condition. @ Armed with all this information, we're ready at last to construct the example map~$(*)$ from the initial permutation $\alpha_0\beta_0\gamma_0\delta_0\varepsilon_0\varphi_0$ in a sensible way, without resorting to trial and error. That map has both $a$ and $b$ attached to vertex~4, with pips $a_0$ and $b_0$ in the vertex ring for~4 in $(**)$. So we can start by splicing $\alpha_0$ and $\beta_0$ together; that means $u_i=a_0$ and~$v_j=b_0$. The splice rule now tells us that $\sigma=(a_0b_0)(a_3b_3)$, because $\alpha_0\beta_0$ takes $a_1\mapsto a_3$ and $\beta_1\mapsto b_3$. Thus we obtain $$\alpha_1=\alpha_0\beta_0\sigma_1=\alpha_0\beta_0(a_0b_0)(a_3b_3)= (a_0b_0)(a_2)(b_2)(a_1b_3b_1a_3).$$ This permutation represents a path of length 2, consisting of edges $a$ and $b$ joined by a common vertex whose pips are $a_0$ and $b_0$. The other two vertices, which have degree~1 because they're endpoints of the path, have the respective pips $a_2$ and $b_2$. The reader is encouraged to draw the corresponding graph of vertices, edges, faces, and pips, so that these ideas become crystal clear. (This graph will be analogous to $(**)$, but it will be considerably simpler because there are only three vertices, two edges, and one face.) Next let's join {\it those\/} two vertices together; we're allowed to do that, even though they belong to the same component, because $a_3$ and $b_3$ belong to the same cycle. The result, with $\sigma_2=(a_2b_2)(a_1b_1)$, is $$\alpha_2=\alpha_1\sigma_2=(a_0b_0)(a_2b_2)(a_1b_3)(a_3b_1),$$ representing a cycle of length 2 between the vertices $(a_0b_0)$ and $(a_2b_2)$. There are two faces, $(a_1b_3)$ and $(a_3b_1)$, either of which can be considered to be the exterior face. In a similar way we can build up a {\it three\/}-cycle from $c$, $d$, and $e$: Letting $\sigma_3=(c_2d_2)(c_1d_1)$, $\sigma_4=(d_0e_2)(d_3e_1)$, and $\sigma_5=(c_0e_0)(c_3e_3)$, we obtain \eqalign{ \gamma_1&=\gamma_0\delta_0\sigma_3= (c_0)(c_2d_2)(d_0)(c_1c_3d_1d_3);\cr \gamma_2&=\gamma_1\varepsilon_0\sigma_4= (c_0)(c_2d_2)(d_0e_2)(e_0)(c_1c_3d_1e_1e_3d_3);\cr \gamma_3&=\gamma_2\varphi\sigma_5= (c_0e_0)(c_2d_2)(d_0e_2)(c_1e_3d_3)(c_3d_1e_1).\cr } Now we can hook $f$ to vertex $(c_0e_0)$, using $\sigma_6=(c_0f_0)(e_3f_3)$: $$\gamma_4=\gamma_3\sigma_6=(c_0e_0f_0)(c_2d_2)(d_0e_2)(f_2) (c_1f_3f_1e_3d_3)(c_3d_1e_1).$$ The two remaining components can be joined together, merging vertices $(a_2b_2)$ and $(c_2d_2)$ appropriately with $\sigma_7=(b_2d_2)(a_1c_1)$: $$\alpha_3=\alpha_2\gamma_4\sigma_7= (a_2d_2c_2b_2)(a_0b_0)(c_0e_0f_0)(d_0e_2)(f_2) (a_1b_3c_1f_3f_1e_3d_3)(a_3b_1)(c_3d_1e_1).$$ And the final coup de gr\^ace hooks $(f_2)$ to $(a_0b_0)$, with $\sigma_8=(f_2a_0)(f_1b_3)$: $$\alpha_4=\alpha_3\sigma_8= (a_0b_0f_2)(a_2d_2c_2b_2)(c_0e_0f_0)(d_0e_2) (a_1f_1e_3d_3)(a_3b_1)(b_3c_1f_3)(c_3d_1e_1).$$ Yes, this is indeed the permutation of $(**)$. We have $$\alpha=\alpha_0\beta_0\gamma_0\delta_0\varepsilon_0\varphi_0\, \sigma_1\sigma_2\sigma_3\sigma_4\sigma_5\sigma_6\sigma_7\sigma_8.$$ One of the main reasons I wrote this program was because I knew that a computer could do these calculations almost instantly, without making silly mistakes. @ So let's write that code. Each pip is conveniently represented by its subscript plus four times the ASCII code of the edge name. For example, $a_3$ would be |('a'<<2)+3|, which is 391 because |'a'=97|. We maintain both $\alpha$ and its inverse $\alpha^-$ in memory, because both representations are useful. If |p| is a pip with |alpha[p]=q|, then |q=alphainv[p]|. (There isn't really a need for both representations, however, because the backup axiom $\alpha^-=\rho\alpha\rho$ always holds.) @d pip(u,i) ((u)<<2)+(i) @d pip_edge(p) ((p)>>2) @d pip_sub(p) ((p)&0x3) @d rot(p) (((p)+1)^(((p)^((p)+1))&-4)) /* $\rho$ */ @d irot(p) (((p)-1)^(((p)^((p)-1))&-4)) /* $\rho^-$ */ @= int alpha[4*256]; /* the permutation of pips describing the current planar map */ int alphainv[4*256]; /* its inverse */ int verts; /* the current number of vertices */ @ We'll permute only the pips for a special {\it root edge\/} and for edges that correspond to nodes in the skew ternary tree that was input. The latter nodes are identifiable because they have left children. (They also have middle and root children. But we don't really care about the children's identities, only their existence.) The root edge is called \.*. @= for (k='*',verts=0;k<='~';k++) if (k=='*' || inputnode[k].left) { alpha[pip(k,0)]=alphainv[pip(k,0)]=pip(k,0); alpha[pip(k,1)]=alphainv[pip(k,1)]=pip(k,3); alpha[pip(k,2)]=alphainv[pip(k,2)]=pip(k,2); alpha[pip(k,3)]=alphainv[pip(k,3)]=pip(k,1); verts+=2; } if (verts!=2*(n+1)) confusion("initial vertex count"); @ The |splice| subroutine is given the addresses of two vertex pips that are supposed to be interchanged. It figures out the two corresponding face pips, using the splice rule mentioned above. We do not worry about the legality'' of a splice, in the sense of preserving planarity, because we'll use |splice| only to reduce the number of vertices. Any illegal usage would cause the final number of faces to be incompatible with Euler's criterion. (Well, there's an exception: In one place below I will splice two pips apart that are adjacent in their vertex cycle. To compensate, I'll increase |verts| by~2.) @= void splice(int p,int q) { register int r,s; if ((p&1) + (q&1)) confusion("attempt to splice face pips"); r=alphainv[p], s=alphainv[q]; alphainv[p]=s, alphainv[q]=r; alpha[s]=p, alpha[r]=q; p=alpha[rot(p)], q=alpha[rot(q)]; /* now swap the appropriate faces */ r=alphainv[p], s=alphainv[q]; alphainv[p]=s, alphainv[q]=r; alpha[s]=p, alpha[r]=q; verts--; } @ Here's a cute subroutine that displays all relevant information about the planar graph by printing $\alpha$'s cycles. First come the pips of the vertex cycles, then the pips of the face cycles, one line at a time. The program also counts the number of vertices and faces, so that it can use Euler's formula to report the number of components (assuming planarity). @= void print_alpha(void) { register int c,f,p,q,r,t,v; @; if (v!=verts) confusion("vertex count"); @; c=(v-(n+1)+f)>>1; printf("(Altogether %d vertices, %d edges, %d faces, %d component%s.)\n", v,n+1,f,c,c==1?"":"s"); } @ The idea is to find a cycle leader (the least |p| whose cycle hasn't already been printed), and to print its cycle, until all cycles for even-numbered pips have been found. @= printf("Vertices:\n"); v=0,p=pip('*',0),t=2*(n+1); while (1) { for (;alpha[p]<=0 && t;p+=2) { if (alpha[p]<0) { /* we've temporarily negated it, see Algorithm 1.3.3I */ alpha[p]=-alpha[p], t--; } } if (t==0) break; /* |t| unprocessed pips remain */ for (q=p,r=alpha[q];r>0;q=r,r=alpha[q]) { printf(" %c%d", pip_edge(r),pip_sub(r)); alpha[q]=-r; } printf("\n"); v++; } @ Exactly the same idea works for odd-numbered pips, of course. @= printf("Faces:\n"); f=0,p=pip('*',1),t=2*(n+1); while (1) { for (;alpha[p]<=0 && t;p+=2) { if (alpha[p]<0) { /* we've temporarily negated it, see Algorithm 1.3.3I */ alpha[p]=-alpha[p], t--; } } if (t==0) break; /* |t| unprocessed pips remain */ for (q=p,r=alpha[q];r>0;q=r,r=alpha[q]) { printf(" %c%d", pip_edge(r),pip_sub(r)); alpha[q]=-r; } printf("\n"); f++; } @*The building blocks of planar graphs. Any connected multigraph is built up in a straightforward treelike way from so-called blocks (aka biconnected components or nonseparable graphs), attached together via so-called articulation points (aka cut vertices). We exclude the trivial cases where a block has fewer than two vertices; in other words, we exclude the empty graph, the one-vertex graph~$K_1$, and the multigraph that consists of a single self-loop. A nontrivial biconnected planar graph is said to be {\it rooted\/} when we place an arrow on one of its edges, converting that edge to a directed arc from $u$ to~$v$ called the root edge. Vertex~$u$ is called the root; and we draw the graph so that the root edge lies on the path that travels counterclockwise around the exterior face. (In other words, the exterior face lies on your right, if you move from $u$ to $v$.) \def\RNBPM/{{\mc RNBPM}} A rooted, nontrivial biconnected planar map (henceforth \RNBPM/'') is an equivalence class of rooted, nontrivial biconnected planar graphs, where two such graphs are said to be equivalent if they're topo\-logically the same when drawn on a sphere as discussed earlier. Thus, each \RNBPM/ can be characterized by its $\alpha$~permutation, except for renaming of the edges and except for adding 2~(mod~4) to the subscripts of any selected subset of the edges. Suppose $r$ is the root edge, and suppose the other edges of the exterior cycle are $e^1$, $e^2$, \dots,~$e^p$. We will define things so that the root vertex cycle contains the pip~$r_0$, hence the exterior face cycle contains the pip~$r_3$. We will also define pip numbers so that $\alpha$ takes $r_0\mapsto e^1_2$, $e^1_0\mapsto e^2_2$, \dots, $e^p_0\mapsto r_2$, so that the exterior face cycle is $(e^p_3\ldots e^2_3e^1_3r_3)$. Exception: If $p=0$, that cycle is of course $(r_1r_3)$. @ The simplest \RNBPM/ consists of just the root edge. Otherwise we can build up any \RNBPM/ recursively in a simple way: Removal of the root edge leaves a graph with $m\ge1$ blocks (hence $m-1$ articulation points); consequently each of those blocks becomes an \RNBPM/ once we identify its root edge. We choose to take the root as the first edge encountered on the exterior face of the full graph, in counterclockwise order. We also take note of the first edge that is {\it not\/} exterior in the full graph, thereby making the block doubly rooted.'' Then the original \RNBPM/ is easily reconstructed from its doubly rooted blocks. Once again we crave an example. Our previous graph $(*)$ will be an \RNBPM/ if we choose any edge~$u$ as a designated root edge, and if we consider the pip $u_3$ to be on its exterior face. But that example is too simple to reveal the general situation; so let's consider something a bit more complex: $$\vcenter{\epsfbox{skew-ternary-calc.40}}\eqno(\dag)$$ Here $m=4$ and the exterior face has $p=7$ other edges; its cycle is therefore $(r_3d^2_3d^1_3c^3_3c^2_3c^1_3b^1_3a^1_3)$. Furthermore the interior face touching~$r$ is $(r_1a^3_3a^2_3b^1_1c^7_3c^6_3c^5_3c^4_3d^3_3)$. If we remove edge~$r$, three articulation points spring up that subdivide the remaining graph into four blocks, having exterior edges identified by the letters $\{a,b,c,d\}$. Block $b$ is just an isthmus, but the other blocks have been built up in turn from smaller constituents. Those larger blocks have been shaded in this diagram, because they may contain complicated interior structure that is invisible from the outside. The four blocks can be regarded as \RNBPM/s, having the respective root edge pips $a^1_3$, $b^1_3$, $c^1_3$, and $d^1_3$. And they're also doubly rooted, because we specify nonroot exterior vertex pips $a^2_2$, $b^1_0$, $c^4_2$, $d^3_2$ that tell us how to hook them together. If $\alpha$, $\beta$, $\gamma$, and~$\delta$ are the permutations corresponding to those blocks, and if $\omega=(r_0)(r_2)(r_1r_3)$ is the permutation for edge~$r$, the permutation for the whole \RNBPM/ is $\alpha\beta\gamma\delta\omega\,\sigma_1\sigma_2\sigma_3\sigma_4\sigma_5$, where $$\sigma_1=(d^3_2r_2)(d^2_3r_1),\quad \sigma_2=(c^4_2d^1_2)(c^3_3d^3_3),\quad \sigma_3=(b^1_0c^1_2)(b^1_3c^7_3),\quad \sigma_4=(a^2_2b^1_2)(a^1_3b^1_1),\quad \sigma_5=(a^1_2r_0)(r_3a^3_3)$$ are the appropriate splicings. @ Here, for handy reference, are the smallest \RNBPM/s and their canonical permutations: \def\\#1{\vcenter{\medskip\epsfbox{skew-ternary-calc.3#1}\medskip}} \vcenter{\halign{\hfil\\#\hfil&\qquad#\hfil\cr 0&(r_0)(r_2)(r_3r_1)\cr 1&(r_0a_2)(a_0r_2)(r_3a_3)(a_1r_1)\cr 2&(r_0a_2b_0)(a_0r_2b_2)(r_3a_3)(a_1b_1)(b_3r_1)\cr 3&(r_0a_2)(a_0b_2)(b_0r_2)(r_3b_3a_3)(a_1b_1r_1)\cr 4&(r_0a_2c_2b_0)(a_0r_2b_2c_0)(r_3a_3)(a_1c_3)(c_1b_1)(b_3r_1)\cr 5&(r_0a_2c_0)(a_0b_2)(b_0r_2c_2)(r_3b_3a_3)(a_1b_1c_1)(c_3r_1)\cr 6&(r_0a_2c_0)(a_0r_2b_2)(b_0c_2)(r_3a_3)(a_1b_1c_1)(c_3b_3r_1)\cr 7&(r_0a_2c_0)(a_0b_2c_2)(b_0r_2)(r_3b_3a_3)(a_1c_1)(c_3b_1r_1)\cr 8&(r_0a_2)(a_0b_2c_0)(b_0r_2c_2)(r_3b_3a_3)(b_1c_1)(a_1c_3r_1)\cr 9&(r_0a_2)(a_0b_2)(b_0c_2)(c_0r_2)(r_3c_3b_3a_3)(r_1a_1b_1c_1)\cr }} @*Planar maps, conform\'ement \a Jacquard et Schaeffer. We return now to our main theme of skew ternary trees. At the very beginning I mentioned that Del Lungo et al found an intriguing correspondence between skew ternary trees and \RNBPM/s. They found it after first having invented the idea of skew ternary trees, and conjecturing that the number of such trees with $n$ nodes is precisely the number of \RNBPM/s with $n$ nonroot edges. Benjamin Jacquard and Gilles Schaeffer responded to that conjecture by finding an ingenious correspondence that is quite different from the one discovered almost simultaneously by Del Lungo et al. [See {\sl Journal of Combinatorial Theory\/ \bf A83} (1998), 1--20.] Naturally I wondered if the two correspondences are somehow related, so I decided to implement both of them in this program. According to their construction, an \RNBPM/ such as $(\dag)$ is represented by a skew ternary tree of the form $$\vcenter{\epsfbox{skew-ternary-calc.41}}\quad\lower15pt\hbox{,}$$ where $A'$, $B'$, $C'$, and $D'$ represent the doubly rooted \RNBPM/s of the $m=4$ blocks that arise when edge~$r$ is removed. Thus the chart corresponding to their representation will have the form $$\vcenter{\epsfbox{skew-ternary-calc.42}}\quad\raise10pt\hbox{,}$$ where $A^*$, $B^*$, $C^*$, and $D^*$ represent the subtrees $A'$, $B'$, $C'$, and $D'$ in some fashion. In this particular example $B'$ is empty, because component $b$ has only a single edge in~$(\dag)$; thus $B^*$ is simply a $+1$ step'' for the bud $\overline2$. But the subtrees $A'$, $C'$, and $D'$ are nonempty (and they might in fact be extremely complicated). The Jacquard--Schaeffer construction also has the property that the total number of rank~0 nodes is always exactly~$p$, the number of nonroot edges on the exterior face of the given \RNBPM/. Consequently the subtrees $D'$ and $C'$ will contain nodes $d^2$, $c^3$, and $c^2$ of rank~0; but $A'$ won't contain any such nodes. @ To complete the construction, we need to explain how to represent a doubly rooted \RNBPM/. Consider, for example, the skew ternary tree $T$ that appeared in the introductory sections at the very beginning of this program: The \RNBPM/ corresponding to $T$ can be used to build larger \RNBPM/s in three different ways, because $T$ has three nodes \.A, \.B, and \.E of rank~0. It turns out that the buds and charts'' method discussed above provides a nice way to encode the second root. The idea is to use one of the three cyclic variants that begin at a bud of rank~$-1$ (namely at bud 1, 2, or~4). Those trees have respectively 2, 1, and 0 nodes of rank~$-1$, and no nodes of rank~$-2$; so they can safely be used as the right subtree $T'$ of a node that has rank~0. For example, the three possibilities for $T^*$ in this example have the following respective charts: \vcenter{\halign{#\hfil\cr \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.81}\cr\noalign{\smallskip} \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.82}\cr\noalign{\smallskip} \epsfxsize=.5\hsize \epsfbox{skew-ternary-calc.84}\cr}} One way to form this is to start at the bud in question and continue creating the chart cyclically until that bud occurs again. The we delete both appearances, and replace it by matching arcs from an assumed parent node \.T to the new subtree root and back. (It follows that a subtree $T'$ of $n$ nodes has a chart $T^*$ of length $4n+1$, even when $n=0$.) Conversely, it's easy to reconstruct $T$ from any of these shifted variants~$T^*$, by undoing the process: First we delete the matching arcs that enclose the whole; then we replace the bud that was deleted. Finally we wind back the cycle until creating a bud with rank $-2$ for the first time. (That bud will be cloned from the rightmost bud of rank~$+2$.) Incidentally, one can show by induction that the number of nodes of odd rank in the skew ternary tree is equal to the number of faces in the corresponding \RNBPM/, minus~2, according to this construction. And the number of nodes of even rank is the number of nonroot vertices. @ Our principal goal is to take a given skew ternary tree and to construct the corresponding \RNBPM/, but computing the quad-tree permutation of that planar map. The tree will be given in chart form. I won't be stingy with memory, so I'll keep a stack of the various charts that arise during the recursion. A tree with |n| nodes will produce an \RNBPM/ with $n$ edges in addition to the root edge. @= step chartstack[maxcodes][4*maxcodes]; /* (only the |first| and |second| fields of these entries are used) */ step tmpchart[4*maxcodes]; int stk[maxcodes*maxcodes]; /* stack of subtrees waiting to be processed */ int curbud; /* the bud whose tree is being mapped (see below) */ @ The |rnbpm_js| routine constructs the Jacquard--Schaeffer \RNBPM/ for |chartstack[s]| with root edge~|r|. A third parameter, |h|, tells the current height of the auxiliary stack |stk|. The value of |stk[h]| is also supposed to identify the root of the skew ternary tree whose chart is in |chartstack[s]|. (The name of the root doesn't appear in the chart when the tree has only one node, hence we need this extra contextual information.) @= void rnbpm_js(int s,int r,int h) { register int i,j,k,l,m,p,q,t,tt,apip,steps; @; apip=pip(r,2); /* pip for attaching blocks */ while (m) { m--, t=stk[h+m]; @; if (m && l>=0 && (chartstack[s][steps].first!=t || chartstack[s][steps].second!=stk[h+m-1])) confusion("arc bracketing"); steps++; if (l<0) @@; else @; @; } @; } @ @= if (chartstack[s][0].second) confusion("no root bud"); for (m=1,steps=1;;m++) { if (chartstack[s][steps++].second) confusion("non skew"); stk[h+m]=chartstack[s][steps++].second; if (stk[h+m]==0) break; } @ At this point we're poised to look at the steps of $T^*$, where $T$ is the subtree that corresponds to edge |t=stk[h+m]|. If $T^*$ is the trivial one-edge \RNBPM/, we set |l=-1|; otherwise we set |l| to the number of nodes in $T^*$ that have rank~0 (which is also the number of buds that have rank~$-1$). In the second case, the subchart $T^*$ is easily identified because it begins with a downward step from |t| to |tt| and ends with a downward step from |tt| to |t|. (These downward steps occur first from rank~1 down to rank~0, then from rank~3 down to rank~2; so they are reminiscent of the German text for quoted text, which begins with \lower1ex\hbox{''} and ends with `$\,$!) We delete those steps and shift the others cyclically backward, in order to deduce $T$ from $T^*$ as explained above. @= if (chartstack[s][steps].second==0) l=-1; else { tt=chartstack[s][steps].second; if (chartstack[s][steps++].first!=t) confusion("wrong parent"); tmpchart[0].first=tmpchart[0].second=0; /* dummy bud */ for (j=1,q=l=0;chartstack[s][steps].second!=t;steps++,j++) { tmpchart[j]=chartstack[s][steps]; if (q==2) k=j; /* remember the location of the last bud with rank 2 */ else if (q==-1) l++; /* count the buds of rank $-1$ */ if (tmpchart[j].second) q--;@+else q++; /* |q| is the rank */ } if (chartstack[s][steps].first!=tt) confusion("right bracket"); for (i=k;i= p=pip(t,1); @ There's a better way to do this step, because we can identify the pip |p| directly while copying the chart. But I didn't have time to stop and figure it out. @= { stk[h+m]=(chartstack[s+1][2].second? chartstack[s+1][2].first: chartstack[s+1][3].second? chartstack[s+1][3].first: tt); rnbpm_js(s+1,t,h+m); for (p=alphainv[pip(t,3)];l;l--) p=alphainv[p]; } @ @= splice(irot(p),apip); apip=pip(t,2); @ @= splice(pip(r,0),apip); @ Okay, |rnbpm_js| is finished. Here's how we apply it to each of the four skew ternary trees of interest. @= for (j=0;j<4;j++) { printf("--- JS map for T"); for (i=0;i; for (i=inputbud[stack[j+offset-2]].stepno,k=0;i<4*n;i++,k++) chartstack[0][k]=chart[i]; for (i=0;i= void rnbpm_ddp(int s, int r) { register int c,i,j,jj,k,p,q,rr,t,steps,parent; @; @; @; @; @; @; } @ The steps of the chart follow preorder. @= if (chartstack[s][0].second) confusion("no root bud"); for (steps=1,q=-1;chartstack[s][steps].second!=sentinel;steps++) { if (q==-1) j=steps; if (chartstack[s][steps].second==0) q++;@+else q--; } if (q!=2) confusion("bad rank at end"); c=chartstack[s][j-1].second; if (c==0) { /* |c| is the root of the charted tree */ if (j!=1) confusion("parentless rank -1 bud not at beginning"); c=chartstack[s][steps].first,p=0; }@+else p=chartstack[s][j-1].first; if (chartstack[s][j+1].second) confusion("not the last zero"); @ If $c$'s right child is just a bud, the subtree $R$ is empty and it corresponds to the empty tree. Otherwise $R$ is bracketed in the chart by arcs from $c$ to its root node and back again, just as the subtree $T^*$ was bracketed in the procedure |rnbpm_js|. In this case the copying task is simpler than it was before, because we needn't count zeros. @= jj=j-1,steps=j+2; rr=chartstack[s][steps].second; if (rr) { /* |rr| is the root of a nonempty subtree $R$ */ if (chartstack[s][steps++].first!=c) confusion("wrong parent"); tmpchart[0].first=tmpchart[0].second=0; /* dummy bud */ for (j=1,q=0;chartstack[s][steps].second!=c;steps++,j++) { tmpchart[j]=chartstack[s][steps]; if (q==2) k=j; /* remember the location of the last bud with rank 2 */ if (tmpchart[j].second) q--;@+else q++; /* |q| is the rank */ } if (chartstack[s][steps].first!=rr) confusion("right bracket"); for (i=k;i= if (rr) rnbpm_ddp(s+1,c); @ If |c| is the root of the tree, then |p| is zero, subtree $\widehat S$ is empty, and nothing needs to be done. Otherwise the tree that corresponds to $\widehat S$ is obtained by simply leaving out |c| and $R$. In the latter case, |jj| points to the arc from |p| to~|c|, and |steps| points to the arc from |c| back to~|p|. @= if (p) { for (i=0;i= if (p) rnbpm_ddp(s+1,r); @ Finally we obey the three-step splicing protocol for $\join c$ that was described above. Some tricky maneuvering is necessary in the degenerate cases. @= if (rr==0) { /* $\widehat T$ is empty */ if (p) splice(pip(c,0),alpha[pip(p,0)]); else splice(pip(c,0),pip(r,2)); }@+else { if (p) splice(pip(c,2),alpha[pip(p,0)]); else splice(pip(c,2),pip(r,2)); splice(pip(c,2),alpha[pip(c,2)]); verts+=2; /* because we spliced two pips from the same vertex */ } splice(pip(c,2),irot(alphainv[pip(r,3)])); @ Okay, |rnbpm_ddp| is finished. Here's how we apply it to each of the four skew ternary trees of interest. @= for (j=0;j<4;j++) { printf("--- DDP map for T"); for (i=0;i; for (i=inputbud[stack[j+offset-2]].stepno,k=0;i<4*n;i++,k++) chartstack[0][k]=chart[i]; for (i=0;i= void confusion(char *id) { /* an assertion has failed */ fprintf(stderr,"This can't happen (%s)!\n",id); exit(-666); } @*Index.