text: CiteSeerX — Citation Query Convex drawings of planar graphs
  Convex drawings of planar graphs
  (1992) by W Schnyder, W Trotter
  Venue:Abstracts of the America Mathematical Society
  ... G can be embedded on a (2n \Gamma 4) \Theta (n \Gamma 2) grid such that all internal faces of G are convex polygons. The grid size of such embedding is reduced to (n \Gamma 2) \Theta (n \Gamma 2) in =-=[3, 13, 21]-=-. It has been observed that there exists a plane graph G, as shown in Fig 1, such that the straight line grid embedding of G requires a grid of size at least (2n=3 \Gamma 1) \Theta (2n=3 \Gamma 1) [9]...
  Convex Grid Drawings of Plane Graphs with . . . by Kazuyuki Miura, Akira Kamada, Takao Nishizeki
  In a convex drawing of a plane graph, all edges are drawn as straightline segments without any edge-intersection and all facial cycles are drawn as convex polygons. In a convex grid drawing, all vertices are put on grid points. A plane graph G has a convex drawing if and only if G is internally triconnected, and an internally triconnected plane graph G has a convex grid drawing on an (n −1) ×(n −1) grid if either G is triconnected or the triconnected component decomposition tree T(G) of G has two or three leaves, where n is the number of vertices in G. In this paper, we show that an internally triconnected plane graph G has a convex grid drawing on a 2n × n 2 grid if T(G) has exactly four leaves. We also present an algorithm to find such a drawing in linear time. Our convex grid drawing has a rectangular contour, while most of the known algorithms produce grid drawings having triangular contours. A Note on Grid Drawings of Plane Graphs
  by Marek Chrobak, Ahmed Radwan
  We consider the problem of drawing plane graphs such that the vertices are represented by grid points and edges are drawn as straight lines. It is an open problem to determine the minimum size ¯ \Theta of grids that admit straight-line drawings of all n-vertex plane graphs. Algorithms are known for producing drawings in grids of size (n \Gamma 2) \Theta (n \Gamma 2) and b2(n \Gamma 1)=3c \Theta b8(n \Gamma 1)=3c. The currently known lower bound is that each dimension satisfies ¯; b2(n \Gamma 1)=3c. In this note, we slightly improve this lower bound by showing that ¯ = b2(n \Gamma 1)=3c implies d2n=3e. Thus it is impossible to achieve the minimum width and height simultaneously. (Show Context)
  ...ed that each 3-connected plane graph has a convex drawing in a (2n \Gamma 4) \Theta (n \Gamma 2) grid, and the grid size was later improved to (n \Gamma 2) \Theta (n \Gamma 2) by Schnyder and Trotter =-=[ST92]-=- and, independently, by Chrobak and Kant [CK93]. In [CN98], Chrobak and Nakano gave an algorithm that produces straight-line drawings in a b2(n \Gamma 1)=3c \Theta b8(n \Gamma 1)=3c grid. All these al...
  ...be constructed by solving a system of linear equations [17]. Linear algorithms that find grid convex drawings with quadratic area for triconnected graphs were given by Kant [10], Schnyder and Trotter =-=[13]-=-, and Chrobak and Kant [6]. Di Battista et al. [2] consider the on-line version of the convex drawing problem. Thomassen [15] gives a necessary and sufficient condition for existence of a convex drawi...