A graph is an optimal right angle crossing graph (also called an optimal RAC graph for short) if it has n vertices and 4n–10 edges and admits a straight-line drawing in the plane such that each edge is crossed at most once and edges cross only at a right angle. This implies that the drawing is 3T- or TTX-framed , that is, the outer face is a triangle that is adjacent to three triangles or to two triangles and a crossing. An optimal pseudo-RAC graph is the topological version of an optimal RAC graph, where the restrictions to straight-line edges and right angle crossings are dropped. We show that every 3T-framed optimal pseudo-RAC graph is an optimal RAC graph, that is, 3T-framed optimal pseudo-RAC embeddings can be stretched and orthogonalized. This is not true for TTX-framed embeddings. There are n -vertex 3T- and TTX-framed optimal RAC graphs for every n ≥ 9 , and eleven optimal RAC and fourteen optimal pseudo-RAC graphs with at most eight vertices. Optimal pseudo-RAC graphs can be recognized in O ( n 3 ) time, where the recognition algorithm demonstrates that every optimal pseudo-RAC graph has at most three 1-planar embeddings, in which edges are crossed at most once.

Many different approaches have been proposed for the challenging problem of visually analyzing large networks. Clustering is one of the most promising. In this paper, we propose a new clustering technique whose goal is that of producing both intracluster graphs and intercluster graph with desired topological properties. We formalize this concept in the (X,Y) -clustering framework, where Y is the class that defines the desired topological properties of intracluster graphs and X is the class that defines the desired topological properties of the intercluster graph. By exploiting this approach, hybrid visualization tools can effectively combine different node-link and matrix-based representations, allowing users to interactively explore the graph by expansion/contraction of clusters without loosing their mental map. As a proof of concept, we describe the system Visual Hybrid (X,Y)-clustering (VHYXY) that implements our approach and we present the results of case studies to the visual analysis of social networks.

If $h_1 $, $h_2 $ are two homomorphisms, then the equality set$\operatorname{Eq}(h_1 ,h_2 )$ of $h_1 $, $h_2 $ is $\operatorname{Eq} (h_1 ,h_2 ) = \{ w | h_1 (w) = h_2 (w)\} $. In this paper it is shown how to characterize complexity classes of formal languages in terms of equality sets of pairs of homomorphisms with bounded balance. In addition the complete twin shuffle language is investigated, and it is shown that for alphabets with at least two letters, this language cannot be represented as the equality set of a pair of homomorphisms unless both homomorphisms are erasing and have linear bounded balance.