Carla Groenland - Graph reconstruction

Distance query reconstruction

In distance query reconstruction, the vertex set is known and you wish to reconstruct the edge set with the minimum number of (adaptive) distance queries (given u,v, what is the shortest path distance between them).

Paul Bastide and Carla Groenland, Optimal distance query reconstruction for graphs without long induced cycles, arXiv:2306.05979.
For graphs without long induced cycles of bounded maximum degree, the optimal query complexity turns out to be \Theta(n log n) in both the randomised and deterministic setting. To show this, we improve both the (previously best) lower and upper bound and derive various interesting corollaries for related settings.
Paul Bastide and Carla Groenland, Quasi-linear distance query reconstruction for graphs of bounded treelength, arXiv:2410.12594 . Conference publication: IPEC 2024.
We provide a randomised algorithm reconstructing graphs of bounded treelength within a quasi-linear number of queries.

Graph reconstruction conjecture

The figure depicts the four induced subgraphs on the four-vertex graph in the bottom, obtained by removing a single vertex and counted with multiplicities. Can you reconstruct what the graph is from its collection of strict induced subgraphs?

Carla Groenland, Tom Johnston, Alex Scott and Jane Tan, Reconstructing trees from small cards, accepted by Israel Journal of Mathematics.
We show a tree on n vertices is already determined by its multiset of induced subgraphs of size about 8n/9. Moreover, we vastly improve on how large subgraphs are needed for reconstructing whether the graph is connected and what the degree sequence is using an unexpected connection: a bound on the number of positive real zeros that a polynomial can have in terms of its coefficients.
Carla Groenland, Tom Johnston, Andrey Kupavskii, Kitty Meeks, Alex Scott and Jane Tan, Reconstructing the degree sequence of a sparse graph from a partial deck. Journal version: Journal of Combinatorial Theory Series B, 157:283-293, 2022.
It is easy to determine the number of edges or the degree sequence when the multiset of one-vertex removed induced subgraphs is given. But what if one or two of them are missing? This turns out to be considerably more difficult.
Carla Groenland, Hannah Guggiari and Alex Scott, Size reconstructibility of graphs, Journal version: Journal of Graph Theory, 96(2):326-337, 2021.

Reconstruction from connected triples

The following paper studies a new reconstruction model introduced by Jeff Erickson, Marc van Kreveld and Jordi L. Vermeulen.

Paul Bastide, Linda Cook, Jeff Erickson, Carla Groenland, Marc van Kreveld, Isja Mannens and Jordi L. Vermeulen, Reconstructing Graphs from Connected Triples, accepted to WG 2023.