Apologies for not knowing exactly what I'm looking for, but I'd appreciate any general pointers to get me started.


I'm interested in efficient representations (graphical and otherwise) of finite graphs with repeated structure --- something like coding theory for graph structures. For example, an $N$ by $N$ grid graph where each non-boundary vertex has four neighbors (up, right, left, down) could be represented with far fewer than O($N^2$) parameters. A $N$ by $N$ grid where each non-boundary vertex has 8 neighbors (up left, up, up right, ...) should take more parameters to represent, but not many more. I'm imagining a notation or diagram that uses a base template, then defines a local connectivity pattern and a repetition structure.


I'd like to be able to ask (and start to answer) questions like:


1. What is the minimum number of parameters needed to describe a particular graph structure?
2. Are there some problems that become fixed-parameter tractable for graphs that can be described with $k$ parameters?


Is there a branch of graph theory that studies these types of questions? I'd be grateful for pointers to starting points or related work.



Representing repeated structure in graphs
I am not sure what exactly is meant by a *repeated structure* but at least some covering graphs should qualify. Covering graphs may be quite large, however they admit concise description via *voltage graphs*. The edges of a small base graph or voltage graph are equipped with group elements, called *voltages*. For instance, an n x n tessellation of a torus can be described by a single vertex with two loops and group elements (0,1) and (1,0) taken from the group $Z\_n \times Z\_n$ assigned to the loops.
Of course most graphs admit no compression in this way. 


