Bounded embeddings of graphs in the plane

A drawing in the plane ($\mathbb{R}^2$) of a graph $G=(V,E)$ equipped with a function $γ: V \rightarrow \mathbb{N}$ is \emph{$x$-bounded} if (i) $x(u) <x(v)$ whenever $γ(u)<γ(v)$ and (ii) $γ(u)\leqγ(w)\leq γ(v)$, where $uv\in E$ and $γ(u)\leq γ(v)$, whenever $x(w)\in x(uv)$, where $x(.)$ denotes the projection to the $x$-axis. We prove a characterization of isotopy classes of graph embeddings in the plane containing an $x$-bounded embedding. Then we present an efficient algorithm, that relies on our result, for testing the existence of an $x$-bounded embedding if the given graph is a tree or generalized $Θ$-graph. This partially answers a question raised recently by Angelini et al. and Chang et al., and proves that c-planarity testing of flat clustered graphs with three clusters is tractable if each connected component of the underlying abstract graph is a tree.

No reviews yet.

No comments yet.