# On bandwidth of graphs

I am trying to find references on algorithms for graphs of bounded bandwidth, in the same way as it is done with treewidth for instance. I could only find research related to computing the bandwidth, or properties of this measure, but not using it as assumption for better algorithms.

Also, I am very interested in a generalization of bandwidth in higher dimensions. For instance this paper studies 2-dimensional bandwidth, but considering only the $L^1$ and $L^\infty$ norms on $\mathbb N\times \mathbb N$, whereas I am more interested in the euclidean norm $L^2$. It seems natural to consider graphs of $n$-dimensional bandwidth for euclidean norm. Formally, the $n$-dimensional bandwidth of a graph $G=(V,E)$ is defined as : $$\min_{\alpha} ~\max_{(x,y)\in E}||\alpha(x)-\alpha(y)||_2$$ where $\alpha$ ranges over injective functions $V\to \mathbb N^n$.

This is pretty natural, for instance graphs coming from discretizations of real-life systems following differential equations would likely have bounded bandwidth. Indeed, if an edge takes you to the state of the system at the next time instant, it can not be too far from your current state if the time step is small enough and the system evolves continuously. It seems that this special structure could be used to design better algorithms (in particular for solving games on these graphs), but I could not find anything on this kind of graphs.

• Are you also interested in results where bandwidth provably doesn't help (e.g. something remains NP-complete even for bounded bandwidth)? Because I have one of those at arxiv.org/abs/1304.5591 May 30 '16 at 22:15
• Yes I am interested in algorithmic problems on graphs of bounded bandwidth, whether it helps or not. My main goal is to solve different kinds of games on these graphs, but I'm curious about other problems too. Thanks for this reference. May 30 '16 at 22:36
• See this paper by Vempala on embedding into 2-d grid. ieeexplore.ieee.org/xpl/… May 31 '16 at 1:16
• You can look at "structural parameterization" where the parameter bandwidth is sometimes used. However, treewidth never exceeds the bandwidth of a graph, therefore all problems FPT w.r.t. treewidth are also for param bandwidth (see section 2 of the PhD. Thesis of Bart Jansen). Also, in the following paper, it is shown that Graph Motif is NP-hard on graphs with bandwidth 4 arxiv.org/abs/1503.05110
– Olf
May 31 '16 at 12:10
• @Florian: thanks for the reference. The relationship with treewidth is only true in one dimension, that's why I would be interested in bounding bandwidth in higher dimension. Jun 1 '16 at 15:11