Network Coding in Planar Networks

A basic problem in network coding is to choose a field to perform the encoding and decoding operations in. The main message we wish to deliver in this talk is that while unboundedly large fields are required in arbitrary networks, very small finite fields may be sufficient for networks in practice. We use planar networks as a representative example of a practical network, which usually has a linear number of links, and exhibits a topology that is planar or close to planar. Focusing on a basic scenario of multicasting two source information flows, we prove that coding over GF(3) is sufficient for all planar networks. We further show that GF(3) is also necessary, by constructing two new planar multicast networks, one of which is a bipartite, that require coding over GF(3) for achieving the maximum throughput. For the special case of outerplanar networks, we prove that network coding is always equivalent to routing. Our results also invite a renewed look at the choice of deterministic vs. randomized network coding in practical networks.