Representing repeated structure in graphs

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.

-
While not strictly a representation of a single graph, there is a very efficient way in principle to represent collections of circuits in a fixed Eulerian graph $G$. It requires the adjacency matrix $A(G)$ and a number of logarithmic bitlength for each circuit (the total number of circuits can be obtained via the matrix-tree and BEST theorems). This fact can be used to define a useful class of entropy measures on sequences that accounts for local autocorrelations. –  Steve Huntsman May 25 '10 at 16:11
There's empirical work motivated by problems such as storing the entire WWW link structure. It's aimed at messier graphs than your examples, but may be related. The Google search "graph compression" takes you to this literature. –  Martin M. W. May 25 '10 at 16:52
The first fork in the road is whether you are chasing labeled graphs or graphs simpliciter, the latter requiring you to think about group-equivalence classes of whatever labeled graphs — or codes of labeled graphs — you have in mind. The computational representation will almost always be more concrete (labeled, rooted, etc.) than you really want. –  Jon Awbrey May 26 '10 at 15:42
If you could give us a concrete example I might try to think about it some more. –  Jon Awbrey Jun 1 '10 at 13:50

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.

-
Thanks. I like this connection to groups. –  Andrew Jul 28 '10 at 19:57

Once you have found the smallest description of a graph (in your favored scheme), then a philosophically minded person will say, Yes, but how about the smallest description-of-a-description of a graph? And how about the smallest description-of-a-description-of-a-description? Why stop?

These ideas will lead you to the concept of Kolmogorov complexity, where one measures the complexity or information content of a mathematical object by the smallest computational description of it, essentially the size of the smallest program that generates the object. The subject is a part of the emerging theory of computational concepts of randomness, an extremely active current area of research in computability theory. The theory is usually thought of as applied to strings: a string is incompressible if the shortest computational description of it has the same size as itself (thus, the most efficient way to describe it is by explicitly listing it out). Compressible strings, in constrast, have comparatively low information density, since they are describable by a much smaller object. Thus, the graphs you seek to describe are exactly the graphs that are compressible with respect to Kolmogorov complexity.

Thus, I propose that we measure the complexity of a graph on vertices $\{1,2,\ldots,n\}$ by the size of the smallest program able to compute the edge relation. (Let us fix for this purpose a notion of computability, such as Turing machines.) This would correspond to the Kolmogorov complexity, and it will be an extremely robust notion of the measure of the complexity of description of your graph. The class of graphs you have in mind are those that are compressible with respect to this measure, computed by a program that is strictly smaller than the program that simply stores the edge relation in state memory.

There is a small paradox in the subject of computational randomness, since ordinarily one might think of a random string as containing very little information, but in this subject, such strings are incompressible, as it is difficult to describe them exactly except by listing them out explicitly. In this sense, therefore, random strings contain a huge amount of information. Similarly, random graphs are hard to describe in any other way other than by listing the edge relation explicitly.

Because of these ideas, your question (perhaps in extreme form) may ultimately have more to do with logic than with graph theory. Almost any mathematical object can be coded into a graph (in a precise sense, every mathematical structure is interpretable inside a graph), and all such mathematical objects can be ultimately described by strings, to which the Kolmogorv ideas apply. You are asking about are the graphs that are compressible in the sense of Kolmogorov complexity. On cardinality grounds, of course, most graphs are not like this. In general, one should expect Turing noncomputability issues to arise, since the question of whether a given string is compressible is undecidable. Similarly, the question of whether a given finite graph is incompressible is undecidable.

-
Thanks. This is very much the kind of description I was looking for. What about the second part? Is it obvious that certain problems on graphs get easier if you can describe the graph with a very small program? Concretely, I'm thinking of something like graphs that can be created programmatically with say $k$ nested for loops and $l$ statements inside the loops (where a statement is only able to create one edge each time it is executed, so these graphs would have at most $k * l$ edges). –  Andrew Jul 28 '10 at 19:10

There are some applications of the design theory to the efficient description of strongly regular graphs. (A strongly regular graph with parameteres ($n$, $k$, $l$, $m$) is a graph with $n$ vertices, in which the number of common neighbours of $x$ and $y$ is $k$, $l$ or $m$ according as $x$ and $y$ are equal, adjacent or non-adjacent.) The desigh theory deals with the questions about subsets of sets which exhibit a high degree of regularity.

Have a look at this book.

-

You can try representing graphical adjacencies in a propositional formula, and then squeeze out redundancies by using some species of canonical form.

I don't recall trying this for arbitrary graphs, but I do recall solving graph coloring problems this way. Here's one link I was able to find right away, an example from Wilf's Algorithms and Complexity (1986).

Graph Coloring Example

What you need to know is that a parenthetical form like $(x_1, \ldots, x_k)$ means that exactly one of the boolean variables $x_1, \ldots, x_k$ is false.

Here's a propositional constraint representation of the 5 queens problem, which may be more suggestive of a way to proceed with your square grid domain.

Five Queens Problem

And here's an exposition of the language and program that I was using to do these examples:

Zeroth Order Logic

-