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 …
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 …
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 …
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 …
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 …
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$ …
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 …
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 …
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 …