Reconstructing graphs from cut-set sizes (Q909677)

The n vertices of a graph embedded in the plane are in general position and the edges are straight line segments between pairs of vertices. A cut-set probe returns the number of edges intersected by a specified line. It is shown that such graphs are completely reconstructible from \(\left( \begin{matrix} n\\ 2\end{matrix} \right)\) cut-set probes and that this number of probes is necessary. For generalised cut-set probes, which determine the size of any cut-set of the graph, \(O(n^ 2/\log n)\) are shown to be necessary and sufficient for reconstruction.