Convex drawing

The boundary of a face may pass straight through one of the vertices of the graph without turning; a strictly convex drawing asks in addition that the face boundary turns at each vertex.

For these graphs, a convex (but not necessarily strictly convex) drawing can be found within a grid whose length on each side is linear in the number of vertices of the graph, in linear time.

[2][3] However, strictly convex drawings may require larger grids; for instance, for any polyhedron such as a pyramid in which one face has a linear number of vertices, a strictly convex drawing of its graph requires a grid of cubic area.

[4] A linear-time algorithm can find strictly convex drawings of polyhedral graphs in a grid whose length on each side is quadratic.

A combinatorial characterization for the graphs with convex drawings is known,[6] and they can be recognized in linear time,[7] but the grid dimensions needed for their drawings and an efficient algorithm for constructing small convex grid drawings of these graphs are not known in all cases.