Skip to main content
MathOverflow

Return to Question

deleted 1 characters in body
Source Link
Andrew
Andrew
  • 341
  • 1
  • 8

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 thenand 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.

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 then 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.

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.

Source Link
Andrew
Andrew
  • 341
  • 1
  • 8

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 then 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.