The Weighted Connectivity Augmentation Problem (WCAP) asks to increase the edge-connectivity of a graph in the cheapest possible way by adding edges from a given set. It is one of the most elementary network design problems for which no better-than-2 approximation algorithm has been known, whereas 2-approximations can be easily obtained through a variety of well-known techniques.

In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5 + ε)-approximation algorithm. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed-solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5 + ε)-approximation algorithm for WCAP.

This is joint work with Rico Zenklusen.

Entangled graphs have a long and involved history in crystallography and more generally the chemical and materials science community. A fairly recent but by now well established idea for their construction and analysis centers around considering embedded graphs on special periodic surfaces as graphs in R^3. This approach has led to the EPINET database of periodic structures produced as embedded graphs on certain triply-periodic minimal surfaces (TPMS).

Characterizing and enumerating embedded graphs up to deformations has only been successful in a relatively small number of cases. Our work to expand the available toolset has recently led to a novel connection between the mapping class group of a (singular) surface, a purely topological object, computational group theory, and entangled (periodic) nets in three-dimensional Euclidean space, bringing topological techniques to bear on a project that is inspired primarily by its applications in other sciences. This connection can be used in a practical combinatorial algorithm for the systematic enumeration of symmetric embedded graphs up to deformations, on TPMS. The graph embeddings on the surface are represented as tilings in the hyperbolic plane. The implementation of this algorithm for certain classes of symmetries has led to a multitude of new and interesting entangled structures in R^3.