Bentz, Cedric


Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

\begin{conjecture} It has been shown that a $k$-outerplanar embedding for which $k$ is minimal can be found in polynomial time. Does a similar result hold for $k$-edge-outerplanar graphs? \end{conjecture}

Keywords: planar graph; polynomial algorithm

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

\begin{conjecture} Is the approximation ratio for the \emph{Maximum Edge Disjoint Paths} (MaxEDP) or the \emph{Maximum Integer Multiflow} problem (MaxIMF) bounded by a constant in $k$-outerplanar graphs or tree-width graphs? \end{conjecture}

Keywords: approximation algorithms; planar graph; polynomial algorithm

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

\begin{conjecture} Can the approximation ratio $O(\sqrt{n})$ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $\mathcal{APX}$-hardness? \end{conjecture}

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

Syndicate content