Graph Theory

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

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?

Keywords: planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

Conjecture   Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in $ k $-outerplanar graphs or tree-width graphs?

Keywords: approximation algorithms; planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

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?

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

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ($ \diamond $)   Let $ L $ be a simple regular ordered $ 2 $-stage graph. Suppose that the graph $ L^m $ is externally connected, for some $ m\ge1 $. Then the graph $ L^{2m} $ is rearrangeable.

Keywords:

Posted by Vadim Lioubimov
updated April 17th, 2010
add new comment | 3 attachments