Convex and strictly convex grid drawings

graph drawing Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graph (discrete mathematics), graphs arising from applications such ...

, a convex drawing of a

planar graph In graph theory, a planar graph is a graph (discrete mathematics), graph that can be graph embedding, embedded in the plane (geometry), plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. ...

is a drawing that represents the vertices of the graph as points in the

Euclidean plane In mathematics, a Euclidean plane is a Euclidean space of Two-dimensional space, dimension two, denoted \textbf^2 or \mathbb^2. It is a geometric space in which two real numbers are required to determine the position (geometry), position of eac ...

and the edges as straight line segments, in such a way that all of the faces of the drawing (including the outer face) have a convex boundary. 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. That is, in a strictly convex drawing, each vertex of the graph is also a vertex of each convex polygon describing the shape of each incident face. Every

polyhedral graph In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the Vertex (geometry), vertices and Edge (geometry), edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyh ...

has a strictly convex drawing, for instance obtained as the

Schlegel diagram In geometry, a Schlegel diagram is a projection of a polytope from \mathbb^d into \mathbb^ through a point just outside one of its facets. The resulting entity is a polytopal subdivision of the facet in \mathbb^ that, together with the ori ...

of a

convex polyhedron In geometry, a polyhedron (: polyhedra or polyhedrons; ) is a three-dimensional figure with flat polygonal faces, straight edges and sharp corners or vertices. The term "polyhedron" may refer either to a solid figure or to its boundary su ...

representing the graph. 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. However, strictly convex drawings may require larger grids; for instance, for any polyhedron such as a

pyramid A pyramid () is a structure whose visible surfaces are triangular in broad outline and converge toward the top, making the appearance roughly a pyramid in the geometric sense. The base of a pyramid can be of any polygon shape, such as trian ...

in which one face has a linear number of vertices, a strictly convex drawing of its graph requires a grid of cubic area. A linear-time algorithm can find strictly convex drawings of polyhedral graphs in a grid whose length on each side is quadratic. Graph homeomorphism example 1

Other graphs that are not polyhedral can also have convex drawings, or strictly convex drawings. Some graphs, such as the

complete bipartite graph In the mathematical field of graph theory, a complete bipartite graph or biclique is a special kind of bipartite graph where every vertex of the first set is connected to every vertex of the second set..Electronic edition page 17. Graph theory ...

K_

, have convex drawings but not strictly convex drawings. A combinatorial characterization for the graphs with convex drawings is known, and they can be recognized in linear time, 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. Convex drawings should be distinguished from

convex embedding In geometric graph theory, a convex embedding of a graph is an embedding of the graph into a Euclidean space, with its vertices represented as points and its edges as line segments, so that all of the vertices outside a specified subset belong to th ...

s, in which each vertex is required to lie within the

convex hull In geometry, the convex hull, convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, ...

of its neighboring vertices. Convex embeddings can exist in dimensions other than two, do not require their graph to be planar, and even for planar embeddings of planar graphs do not necessarily force the outer face to be convex.

References

{{reflist, refs= {{citation , last = Andrews , first = George E. , doi = 10.2307/1993769 , journal = Transactions of the American Mathematical Society , mr = 143105 , pages = 270–279 , title = A lower bound for the volume of strictly convex bodies with many boundary lattice points , volume = 106 , year = 1963, issue = 2 , jstor = 1993769 , doi-access = free {{citation , last1 = Bárány , first1 = Imre , author1-link = Imre Bárány , last2 = Rote , first2 = Günter , arxiv = cs/0507030 , journal = Documenta Mathematica , mr = 2262937 , pages = 369–391 , title = Strictly convex drawings of planar graphs , volume = 11 , year = 2006, doi = 10.4171/dm/214 , doi-access = free , s2cid = 47071207 {{citation , last1 = Bonichon , first1 = Nicolas , last2 = Felsner , first2 = Stefan , last3 = Mosbah , first3 = Mohamed , doi = 10.1007/s00453-006-0177-6 , issue = 4 , journal = Algorithmica , mr = 2304987 , pages = 399–420 , title = Convex drawings of 3-connected plane graphs , volume = 47 , year = 2007, s2cid = 375595 {{citation , last1 = Chiba , first1 = Norishige , last2 = Yamanouchi , first2 = Tadashi , last3 = Nishizeki , first3 = Takao , editor1-last = Bondy , editor1-first = J. Adrian , editor2-last = Murty , editor2-first = U. S. R. , contribution = Linear algorithms for convex drawings of planar graphs , mr = 776799 , pages = 153–173 , publisher = Academic Press , title = Progress in graph theory (Waterloo, Ont., 1982) , year = 1984 {{citation , last = Kant , first = G. , doi = 10.1007/s004539900035 , issue = 1 , journal = Algorithmica , mr = 1394492 , pages = 4–32 , title = Drawing planar graphs using the canonical ordering , volume = 16 , year = 1996, hdl = 1874/16676 , hdl-access = free {{citation , last1 = Linial , first1 = N. , author1-link = Nati Linial , last2 = Lovász , first2 = L. , author2-link = László Lovász , last3 = Wigderson , first3 = A. , author3-link = Avi Wigderson , doi = 10.1007/BF02122557 , issue = 1 , journal = Combinatorica , mr = 951998 , pages = 91–102 , title = Rubber bands, convex embeddings and graph connectivity , volume = 8 , year = 1988, s2cid = 6164458 {{citation , last = Thomassen , first = Carsten , doi = 10.1016/0095-8956(80)90083-0 , issue = 2 , journal = Journal of Combinatorial Theory , mr = 586436 , pages = 244–271 , series = Series B , title = Planarity and duality of finite and infinite graphs , volume = 29 , year = 1980, doi-access = free {{citation , last = Tutte , first = W. T. , authorlink = W. T. Tutte , doi = 10.1112/plms/s3-10.1.304 , journal = Proceedings of the London Mathematical Society , mr = 114774 , pages = 304–320 , series = Third Series , title = Convex representations of graphs , volume = 10 , year = 1960 {{citation , last1 = Zhou , first1 = Xiao , last2 = Nishizeki , first2 = Takao , doi = 10.1142/S179383091000070X , issue = 3 , journal = Discrete Mathematics, Algorithms and Applications , mr = 2728831 , pages = 347–362 , title = Convex drawings of internally triconnected plane graphs on

O(n^2)

grids , volume = 2 , year = 2010 Graph drawing Planar graphs