A note on planar graphs with large width parameters and small grid-minors

作者：Grigoriev Alexander^*; Marchal Bert; Usotskaya Natalya; Todinca Ioan

来源：Discrete Applied Mathematics, 2012, 160(7-8): 1262-1269.

DOI：10.1016/j.dam.2012.01.007

• Planar graph
• Tree-width
• Branch-width
• Grid-minor

Given a graph G with tree-width omega(G), branch-width beta(G), and side size of the largest square grid-minor theta(G), it is known that theta(G) %26lt;= beta(G) %26lt;= omega(G) + 1 %26lt;= 3/2 beta(G). In this paper, we introduce another approach to bound the side size of the largest square grid-minor specifically for planar graphs. The approach is based on measuring the distances between the faces in an embedding of a planar graph. We analyze the tightness of all derived bounds. In particular, we present a class of planar graphs where theta(G) = beta(G) %26lt; omega(G) = left perpendicular3/2 theta(G)right perpendicular - 1.

• 出版日期2012-5