What should we add?

The generation of random circuits should be extended by the ability to specify a circuit connectivity or interaction graph $G$ that the random graph should should adhere to. The interaction graph $G$ of a circuit is determined by the set of two-qubit gate interactions $g_{1}=(v_{1}, u_{1}), ..., g_{n}=\{v_{n},u_{n}\}$ with qubits $V=\{v_{i}\}$ in the circuit such that $G=(V, E)$ where $E=\{g_{i}\}$. You can generate the interaction graph of a circuit using vf2_utils.build_interaction_graph. For instance, let $G=(V, E)$ be a line graph over $n$ qubits such that $E=\{\{v_{i}, v_{i+1}\} | $ for $i=0...n-2$ $\}$, then each two-qubit gate in the random circuit may only interact on neighboring qubits $v_{i}, v_{i+1}$.

To realize this behavior, please create a new function random_circuit_from_graph to https://github.com/Qiskit/qiskit/blob/main/qiskit/circuit/random/utils.py with the parameters
interaction_graph, max_operands=2, measure=False, conditional=False, reset=False, seed=None that represents the graph $G$ as above. The number of vertices in interaction_graph define the number of qubits in the circuit to be generated and the depth parameter specifies how often each qubit-pair must at least be used in a two-qubit gate before the circuit is returned. The remaining parameters should follow the definition of random_circuit in https://github.com/Qiskit/qiskit/blob/main/qiskit/circuit/random/utils.py#L23.

Optional edge weights in interaction_graph must be positive and should be normalized to sum up to 1.0. The now normalized edge weights represent the probability with which each qubit-pair interaction is inserted into a layer. An uniform edge weight would indicate that each two-qubit gate between the pairs specified in interaction_graph are equally likely to get inserted into a layer of the generated random circuit.

Please also add tests to validate your changes and add a release note according to https://github.com/Qiskit/qiskit/blob/main/CONTRIBUTING.md

Note that this is a subtask of #11718 and connected to #12059. :-)