Documentation: See libpkg-guide, especially Chapter 6. Development (-DEV) packages, paragraph 2. -DEV package dependencies

Question: How to compute this dependencies?

Answer: By checking the NEEDED entries of the provided .so files, which can be automated thanks to d-devlibdeps from the d-shlibs package (thanks Junichi!).

Usage: an example taken from graphviz. Before the split from debian/tmp to debian/$package happens (important: the symlinks would be broken otherwise), it is sufficient to call:

d-devlibdeps \
    --override s/libpathplan3-dev// \
    --override s/libgraph3-dev//    \
    --override s/libcdt3-dev//      \
    $(CURDIR)/debian/libgraphviz3-dev.substvars \
    $(CURDIR)/debian/tmp/usr/lib/*.so

The overrides are needed because there are some .so dependending on others belonging to the same package, so there's no need to search for another package containing them, d-devlibdeps would even fail.

The output is written to the debian/libgraphviz3-dev.substvars file, which is automatically used by dh_gencontrol.

It is then sufficient to put a Depends: ${devlibs:Depends} in the control file, and that's all, folks!