Grid drawings of 4-connected plane graphs (Q5939541)

A grid drawing of a plane graph \(G\) on a \(w\times h\) grid is a drawing of \(G\) in the plane in which the vertices are put on grid points with integer coordinates \((x,y)\), \(0\leq x\leq w\), \(0\leq y\leq h\) and the edges are drawn as straight line segments intersecting only at common endpoints. The authors present a linear-time algorithm which finds a grid drawing of a given 4-connected plane graph of order \(n\) which has at least four vertices on the outer face on a \((\lceil n/2\rceil-1)\times\lfloor n/2\rfloor\) grid. This improves a previous result of \textit{X.~He} [Discrete Comput. Geom. 17, No. 3, 339-358 (1997; Zbl 0877.05014)] whose algorithm provides a drawing on a \(w\times h\) grid, \(w\leq(n+3)/2\), \(h\leq 2(n-1)/3\) and \(w+h\leq n\). The construction is based on the 4-canonical ordering introduced by \textit{G.~Kant} and \textit{X.~He} [Theor. Comput. Sci. 172, No. 1-2, 175-193 (1997; Zbl 0903.68137)] and uses a simple idea of dividing a given plane graph into two subgraphs, drawing each of them in an isosceles right-angled triangle and combining both drawings. It is also shown that the bounds are the best possible by exposing an infinite class of 4-connected plane graphs any grid drawing of which requires a grid of size at least \((\lceil n/2\rceil-1)\times\lfloor n/2\rfloor\).