# Routing a DAG through 5 consecutive butterfly networks

I have two questions concerning the paper Nearly linear-size holographic proofs. In the second paragraph of section 6, A Graph Coloring Problem, it is claimed that

Using standard packet-routing techniques [Lei92], we can find switching actions for each node that establish collision-free paths in the graph for each packet.

The goal is to emulate a circuit (containing $$m$$ (arity 1 and 2 only ?) gates and $$n$$ inputs) using 5 consecutive copies of the butterly network of order $$r$$ (where $$2^r\geq n+m$$).

## First question

1. Where do I find the quoted result in [Lei92] ?

I am unable to locate the relevant result in Introduction to parallel Algorithms and Architectures, F.T. Leighton. I didn't find anything on the internet either when looking for "embedding directed acyclic graphs in butterfly networks" for instance. I found many interesting results about routing permutations, and there is a whole section that talks about packet routing, but I can't find what the authors quote...

In the following paragraph, the authors discuss the labels one may put on nodes. In particular they write that there are

4 switches (depending on how you count them)

It would seem most natural to me to have

• the empty switch : we won't be routing anything through here
• two "single wire going straight ahead" kind of switches
• two "single wire making a switch" kind of switches
• two fan-out switches
• one "two wires coming in and going straight ahead" kind of swich
• one "two wires coming in and making a switch" kind of switch

for a total of 9 natural'' switch types for intermediate nodes in the router. I can see that the 9 switches I describe can be clustered in 4 categories

• empty (only 1 of this kind)
• 1-1 (single wire in, single wire out : 4 of this kind),
• 1-2 (fan out : 2 of this kind),
• 2-2 (two wires in, two wires out : 2 of this kind)

## Second question

1. Why would the authors only talk of 4 switches ? Is this somehow more natural than ?