Graph Embeddings

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 …

Strip Planarity Testing for Embedded Planar Graphs

In this paper we introduce and study the Strip Planarity Testing problem, which takes as an input a planar graph $G(V,E)$ and a function $\gamma:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is …

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 …

Algorithms and bounds for drawing non-planar graphs with crossing-free subgraphs

We initiate the study of the following problem$:$ Given a non-planar graph $G$ and a planar subgraph $S$ of $G$, does there exist a straight-line drawing $\Gamma$ of $G$ in the plane such that the edges of $S$ are not crossed in $\Gamma$? We give …

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 …

Anchored Drawings of Planar Graphs

In this paper we study the ANCHORED GRAPH DRAWING (AGD) problem$:$ Given a planar graph $G$, an initial placement for its vertices, and a distance $d$, produce a planar straight-line drawing of $G$ such that each vertex is at distance at most $d$ …

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 …

Drawing Non-Planar Graphs with Crossing-Free Subgraphs

We initiate the study of the following problem$:$ Given a non-planar graph $G$ and a planar subgraph $S$ of $G$, does there exist a straight-line drawing $\Gamma$ of $G$ in the plane such that the edges of $S$ are not crossed in $\Gamma$? We give …

Strip Planarity Testing

In this paper we introduce and study the strip planarity testing problem, which takes as an input a planar graph $G(V,E)$ and a function $\gamma:V \rightarrow \{1,2,\dots,k\}$ and asks whether a planar drawing of $G$ exists such that each edge is …