# SPQR-Trees

## Reaching 3-Connectivity via Edge-edge Additions

Given a graph $G$ and a pair $\langle e',e''\rangle$ of distinct edges of $G$, an edge-edge addition on $\langle e',e''\rangle$ is an operation that turns $G$ into a new graph $G'$ by subdividing edges $e'$ and $e''$ with a dummy vertex $v'$ and …

## Approximation Algorithms for Facial Cycles in Planar Embeddings

Consider the following combinatorial problem$:$ Given a planar graph $G$ and a set of simple cycles $\mathcal C$ in $G$, find a planar embedding $\mathcal E$ of $G$ such that the number of cycles in $\mathcal C$ that bound a face in $\mathcal E$ is …

## Simultaneous Orthogonal Planarity

We introduce and study the OrthoSEFE-$k$ problem$:$ Given~$k$ planar graphs each with maximum degree 4 and the same vertex set, is there an assignment of the vertices to grid points and of the edges to paths on the grid such that the same edges in …

## Planar Graphs with Vertices in Prescribed Regions: models, algorithms, and complexity

The volume and the complexity of structured relational information created and handled by modern information systems has drastically increased. More and more often, data are generated so quickly that they cannon even be completely displayed or …

## Relaxing the constraints of clustered planarity

In a drawing of a clustered graph vertices and edges are drawn as points and curves, respectively, while clusters are represented by simple closed regions. A drawing of a clustered graph is c-planar if it has no edge-edge, edge-region, or …

## Planar Embeddings with Small and Uniform Faces

Motivated by finding planar embeddings that lead to drawings with favorable aesthetics, we study the problems MINMAXFACE and UNIFORMFACES of embedding a given biconnected multi-graph such that the largest face is as small as possible and such that …