Grid embedding of 4-connected plane graphs (Q1355197)

Let \(G\) be a graph represented in the plane so that each edge corresponds to a straight line and any two such lines intersect only at common endpoints. If each vertex of \(G\) corresponds to a point with integer coordinates \((x,y)\) where \(0\leq x\leq n\) and \(0\leq y\leq m\), then we speak of an \(n\times m\) grid representation. It is known that every planar graph of order \(n\) admits an \(n\times n\) grid representation, and that there are \(n\)-vertex graphs which need at least a \(2n/3\times 2n/3\) grid. It is also conjectured that such a grid accommodates every plane graph of order \(n\). In this paper it is shown that if a 4-connected plane graph \(G\) of order \(n\) has at least 4 vertices on its external face, then \(G\) can be represented by a \(w\times h\) grid where \(w+ h\leq n\), \(w\leq(n+3)/2\), and \(h\leq 2(n-1)/3\). Such a representation can be found in linear time.