|dc.description.abstract||Network coding, a relatively new paradigm for transmitting information through communication networks,
allowing intermediate nodes in the network to combine data received on separate incoming channels
before transmitting on outgoing channels. When compared with traditional routing paradigms, network
coding can result in benefits such as higher throughput, fault-tolerance, and security.
In this paper, we focus on studying network coding properties on a specific class of graphs called grid
graphs. Network coding properties are related to well-known Steiner properties in graphs. Specifically,
Steiner properties of grid graphs are studied, because they model VLSI layout design, which makes network
coding properties a natural extension of this investigation.
In particular, we looked at the maximum size of a communication group that is possible in a grid graph,
given a specific desired transmission rate. Letting rk (G) be the maximum fraction of nodes in graph G that
can be included in a network coded multicast group with an integral flow of size k, we prove that r2(G)<1,
r3(G) < 1
2 , and r4(G) < 1
3 . In the first two cases, we construct families of communication groups on grid
graphs which approach these bounds. In the latter case, we present a family of communication groups
approaching a density of 14