Search

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\}$$?:V?{1,2,?,k} and asks whether a planar drawing of G exists such that each edge is represented by a curve that is monotone in the y-direction and, for any $$u,v\in V$$u,v?V with $$\gamma (u)

Consider an n-vertex planar graph G. The depth of an embedding Γ of G is the maximum distance of its internal faces from the external one. Several researchers pointed out that the quality of a planar embedding can be measured in terms of its depth. We present an O(n 4)-time algorithm for computing an embedding of G with minimum depth. This bound improves on the best previous bound by an O(nlog n) factor. As a side effect, our algorithm improves the bounds of several algorithms that require the computation of a minimum-depth embedding.

We consider the problem of maintaining on-line the triconnected components of a graphG. Letn be the current number of vertices ofG. We present anO(n)-space data structure that supports insertions of vertices and edges, and queries of the type "Are there three vertex-disjoint paths between verticesv1 andv2?" A sequence ofk operations takes timeO(k·ź(k, n)) ifG is biconnected(ź(k, n) denotes the well-known Ackermann's function inverse), and timeO(n logn+k) ifG is not biconnected. Note that the bounds do not depend on the number of edges ofG. We use theSPQR-tree, a versatile data structure that represents the decomposition of a biconnected graph with respect to its triconnected components, and theBC-tree, which represents the decomposition of a connected graph with respect to its biconnected components.