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 the convex hull of their neighbors. More precisely, if is a subset of the vertices of the graph, then a convex -embedding embeds the graph in such a way that every vertex either belongs to or is placed within the convex hull of its neighbors. A convex embedding into -dimensional Euclidean space is said to be in general position if every subset of its vertices spans a subspace of dimension .[1]

Convex embeddings were introduced by W. T. Tutte in 1963. Tutte showed that if the outer face of a planar graph is fixed to the shape of a given convex polygon in the plane, and the remaining vertices are placed by solving a system of linear equations describing the behavior of ideal springs on the edges of the graph, then the result will be a convex -embedding. More strongly, every face of an embedding constructed in this way will be a convex polygon, resulting in a convex drawing of the graph.[2]

Beyond planarity, convex embeddings gained interest from a 1988 result of Nati Linial, László Lovász, and Avi Wigderson that a graph is k-vertex-connected if and only if it has a -dimensional convex -embedding in general position, for some of of its vertices, and that if it is k-vertex-connected then such an embedding can be constructed in polynomial time by choosing to be any subset of vertices, and solving Tutte's system of linear equations.[1]

One-dimensional convex embeddings (in general position), for a specified set of two vertices, are equivalent to bipolar orientations of the given graph.[1]

References

edit
  1. ^ a b c Linial, N.; Lovász, L.; Wigderson, A. (1988), "Rubber bands, convex embeddings and graph connectivity", Combinatorica, 8 (1): 91–102, doi:10.1007/BF02122557, MR 0951998, S2CID 6164458
  2. ^ Tutte, W. T. (1963), "How to draw a graph", Proceedings of the London Mathematical Society, 13: 743–767, doi:10.1112/plms/s3-13.1.743, MR 0158387.