Graph-product structure conjecture for -nearest-neighbour graphs
Graph-product structure conjecture for -nearest-neighbour graphs
A finite set defines a -nearest-neighbour graph by joining two points whenever one is among the points closest to the other. Here, denotes the strong product of a graph and the -dimensional integer lattice, and is a function of and . Graph-product structure conjecture. Every -nearest-neighbour graph in is a subgraph of
for some graph with treewidth at most . 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 -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.