Relational data is omnipresent in our computerized society and has found its way into our everyday life: Circumstances in social networks, in the transport- and public mains supply, as well as in politics or academics can be modeled with relational data. However, together with the ever-growing amount of this data type also novel analysis techniques have to be developed that are able to cope with its demanding size and complexity properties. Typical tasks include not only visualizing the often large and dense data but also helping the analyst to understand relationships if the data set is multivariate or dynamic in nature. Several well-known visualization techniques for relational data exist. For example, node-link diagrams display relationship attributes by drawing edges between nodes with respect to the relationship strength. The layout of nodes helps users to perceive groupings, central items, or highly connected items. Matrix-based representations are another means to visualize relational data. This compact representation reaches its technical scalability limit not until all display pixels are occupied. In this doctoral thesis, we will present novel visual interactive techniques, algorithmic approaches, and integrated visual analytics systems to support users in navigating and exploring large amounts of relational data. One central research objective is, amongst others, to automatically assess the interestingness of matrix views and show only potentially relevant matrices from a large exploration space to reduce the users’ cognitive overload.