Constant-factor approximations of branch-decomposition and largest grid minor of planar graphs in <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si2.gif" display="inline" overflow="scroll"><mml:mi>O</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:msup><mml:mrow><mml:mi>n</mml:mi></mml:mrow><mml:mrow><mml:mn>1</mml:mn><mml:mo>+</mml:mo><mml:mi>ϵ</mml:mi></mml:mrow></mml:msup><mml:mo>)</mml:mo></mml:mrow></mml:math> time
We give constant-factor approximation algorithms for computing the optimal branch-decompositions and largest grid minors of planar graphs. For a planar graph G with n vertices, let bw ( G ) be the branchwidth of G and gm ( G ) the largest integer g such that G has a g × g grid as a minor. Let c ≥ 1 be a fixed integer and α , β arbitrary constants satisfying α > c + 1 and β > 2 c + 1 . We give an algorithm which constructs in O ( n 1 + 1 c log n ) time a branch-decomposition of G with width at most α bw ( G ) . We also give an algorithm which constructs a g × g grid minor of G with g ≥ gm ( G ) β in O ( n 1 + 1 c log n ) time. The constants hidden in the Big-O notations are proportional to c α − ( c + 1 ) and c β − ( 2 c + 1 ) , respectively.