Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group's shape carries meaning as well. In this paper, we represent a group's shape using a simple geometric object, a line segment. Specifically, given a radius $r$, we say a line segment is representative of a point set $P$ if it is within distance $r$ of each point $p \in P$. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius $r$ using the shortest line segment. We describe an algorithm to find the shortest representative segment in $O(n \log h + h \log^3 h)$ time. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in $P$ move.

Visualizing a graph directly via its adjacency matrix is a common and effective technique. Such matrix visualizations rely crucially on a good ordering of the vertices to highlight intrinsic patterns in the graph. When analyzing collections of graphs, such as time varying sequences or connectivity information ranging over multiple specimens, the user currently needs to make the choice: either order each graph individually to optimize its ordering quality, or use a single, simultaneous ordering for all graphs in the collection, which necessarily reduces the ordering quality for the individual graphs.In this paper we explore the space of contextual orderings that lie between these two extremes. Intuitively, contextual orderings maintain a higher level of consistency than individual orderings and deliver a higher ordering quality than simultaneous orderings. To formally reason about contextual orderings we define a distance measure between orderings which is based on individual block moves (IBM). The IBM distance allows us to relate consistency within the context of the collection with ordering quality. Specifically, we define the consistency of an ordering as the IBM distance to the simultaneous ordering for the collection. Our experiments show that already at a small IBM distance to the simultaneous ordering we can find contextual orderings with significantly improved ordering quality. Furthermore, we can create orderings that are nearly as good as individual orderings, but exhibit considerably improved consistency. We hence believe that contextual orderings can enable a more fine-grained analysis of graph collections, by allowing the user to focus on individual graphs while maintaining a sense of the context they appear in.

Undirected graphs are frequently used to model phenomena that deal with interacting objects, such as social networks, brain activity and communication networks. The topology of an undirected graph G can be captured by an adjacency matrix; this matrix in turn can be visualized directly to give insight into the graph structure. Which visual patterns appear in such a matrix visualization crucially depends on the ordering of its rows and columns. Formally defining the quality of an ordering and then automatically computing a high-quality ordering are both challenging problems; however, effective heuristics exist and are used in practice. Often, graphs do not exist in isolation but as part of a collection of graphs on the same set of vertices, for example, brain scans over time or of different people. To visualize such graph collections, we need a single ordering that works well for all matrices simultaneously. The current state-of-the-art solves this problem by taking a (weighted) union over all graphs and applying existing heuristics. However, this union leads to a loss of information, specifically in those parts of the graphs which are different. We propose a collection-aware approach to avoid this loss of information and apply it to two popular heuristic methods: leaf order and barycenter.The de-facto standard computational quality metrics for matrix ordering capture only block-diagonal patterns (cliques). Instead, we propose to use Moran's I, a spatial auto-correlation metric, which captures the full range of established patterns. Moran's I refines previously proposed stress measures. Furthermore, the popular leaf order method heuristically optimizes a similar measure which further supports the use of Moran's I in this context. An ordering that maximizes Moran's I can be computed via solutions to the Traveling Salesperson Problem (TSP); orderings that approximate the optimal ordering can be computed more efficiently, using any of the approximation algorithms for metric TSP. We evaluated our methods for simultaneous orderings on real-world datasets using Moran's I as the quality metric. Our results show that our collection-aware approach matches or improves performance compared to the union approach, depending on the similarity of the graphs in the collection. Specifically, our Moran's I-based collection-aware leaf order implementation consistently outperforms other implementations. Our collection-aware implementations carry no significant additional computational costs.