Graph-product structure conjecture for kk-nearest-neighbour graphs

A finite set PRdP\subset\mathbb{R}^d defines a kk-nearest-neighbour graph by joining two points whenever one is among the kk points closest to the other. Here, HZd1H\boxtimes\mathbb{Z}^{d-1} denotes the strong product of a graph HH and the (d1)(d-1)-dimensional integer lattice, and f(k,d)f(k,d) is a function of kk and dd. Graph-product structure conjecture. Every kk-nearest-neighbour graph in Rd\mathbb{R}^d is a subgraph of

HZd1H\boxtimes\mathbb{Z}^{d-1}

for some graph HH with treewidth at most f(k,d)f(k,d). This would describe these geometric graphs through a strong product with a fixed-dimensional lattice and a factor of bounded treewidth, complementing known separator results for kk-nearest-neighbour graphs. The source poses this as a question and gives no resolution.

Sources & referencesView supporting material

Primary source

Zdeněk Dvořák, Tony Huynh, Gwenaël Joret, Chun-Hung Liu and David R. Wood, “Notes on Graph Product Structure Theory”, arXiv:2001.08860 (2020).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.