Near symmetric structures or products

In this theme the main topics are graph products and graph representations using (algebraic) structures that give rise to highly regular and/or symmetric families of graphs.Large graphs arise in many contexts and are easier to handle in practice if they have a specialized structure (tree-like, median-graph like, or similar to one of the standard graph products). In real-life applications, special properties can often be expected to hold only “approximately”, however. The research will therefore focus on two aspects: (1) detailed characterizations of classes suitable to recognize symmetric or product-like structures in real data and (2) development of efficient algorithms for recognition of approximate products or nearly symmetric graphs (using spectral properties, degree sequences, novel local measures of graph structures, relationships between symmetries or product structures and other algebraic descriptions). Generalization from simple graphs to digraphs and various types of hypergraphs will also be studied. We will deal with detection of large (induced) subgraphs that approximately adhere to certain desirable graph properties, recognition of (approximate) graph products and approximation of large graphs by products. The results from this theme will have important implications in large networks visualization.

Involved: Leydold, Stadler, Biyikoglu, Klavžar, Imrich