\input zb-basic
\input zb-ioport
\iteman{io-port 06102420}
\itemau{Di Giacomo, Emilio; Didimo, Walter; Liotta, Giuseppe; Montecchiani, Fabrizio}
\itemti{$h$-quasi planar drawings of bounded treewidth graphs in linear area.}
\itemso{Golumbic, Martin Charles (ed.) et al., Graph-theoretic concepts in computer science. 38th international workshop, WG 2012, Jerusalem, Israel, June 26--28, 2012. Revised selcted papers. Berlin: Springer (ISBN 978-3-642-34610-1/pbk). Lecture Notes in Computer Science 7551, 91-102 (2012).}
\itemab
Summary: We study the problem of computing $h$-quasi planar drawings in linear area; in an $h$-quasi planar drawing the number of mutually crossing edges is at most $h - 1$. We prove that every $n$-vertex partial $k$-tree admits a straight-line $h$-quasi planar drawing in $O(n)$ area, where $h$ depends on $k$ but not on $n$. For specific sub-families of partial $k$-trees, we present ad-hoc algorithms that compute $h$-quasi planar drawings in linear area, such that $h$ is significantly reduced with respect to the general result. Finally, we compare the notion of $h$-quasi planarity with the notion of $h$-planarity, where each edge is allowed to be crossed at most $h$ times.
\itemrv{~}
\itemcc{}
\itemut{}
\itemli{doi:10.1007/978-3-642-34611-8\_12}
\end