  In this paper we introduce extensions and modifications of the classical
degree sequence graphic realization problem studied by Erd\H{o}s-Gallai and
Havel-Hakimi, as well as of the corresponding connected graphic realization
version. We define the joint-degree matrix graphic (resp. connected graphic)
realization problem, where in addition to the degree sequence, the exact number
of desired edges between vertices of different degree classes is also
specified. We give necessary and sufficient conditions, and polynomial time
decision and construction algorithms for the graphic and connected graphic
realization problems. These problems arise naturally in the current topic of
graph modeling for complex networks. From the technical point of view, the
joint-degree matrix realization algorithm is straightforward. However, the
connected joint-degree matrix realization algorithm involves a novel recursive
search of suitable local graph modifications. Also, we outline directions for
further work of both theoretical and practical interest. In particular, we give
a Markov chain which converges to the uniform distribution over all
realizations. We show that the underline state space is connected, and we leave
the question of the mixing rate open.
