Convex embedding

In <a href="/facts/Geometric_graph_theory/4vIAySX3">geometric graph theory</a>, a convex embedding of a graph is an embedding of the graph into a <a href="/facts/Euclidean_space/R2UbzmzM">Euclidean space</a>, with its vertices represented as points and its edges as <a href="/facts/Line_segment/V8E0M4qk">line segments</a>, so that all of the vertices outside a specified subset belong to the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of their neighbors. More precisely, if 
 
 
 
 X
 
 
 {\displaystyle X}
 
 is a subset of the vertices of the graph, then a convex 
 
 
 
 X
 
 
 {\displaystyle X}
 
-embedding embeds the graph in such a way that every vertex either belongs to 
 
 
 
 X
 
 
 {\displaystyle X}
 
 or is placed within the convex hull of its neighbors. A convex embedding into 
 
 
 
 d
 
 
 {\displaystyle d}
 
-dimensional Euclidean space is said to be in <a href="/facts/General_position/p0YpbkJv">general position</a> if every subset 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of its vertices spans a subspace of dimension 
 
 
 
 min
 (
 d
 ,
 
 |
 
 S
 
 |
 
 −
 1
 )
 
 
 {\displaystyle \min(d,|S|-1)}
 
.
Convex embeddings were introduced by <a href="/facts/W._T._Tutte/8VbfbzU6">W. T. Tutte</a> in 1963. Tutte showed that if the outer face 
 
 
 
 F
 
 
 {\displaystyle F}
 
 of a <a href="/facts/Planar_graph/plREagr9">planar graph</a> is fixed to the shape of a given convex polygon in the plane, and the remaining vertices are placed by solving a <a href="/facts/System_of_linear_equations/fk9CFdgp">system of linear equations</a> describing the behavior of ideal springs on the edges of the graph, then the result will be a convex 
 
 
 
 F
 
 
 {\displaystyle F}
 
-embedding. More strongly, every face of an embedding constructed in this way will be a convex polygon, resulting in a <a href="/facts/Convex_drawing/8gklpVqF">convex drawing</a> of the graph.
Beyond planarity, convex embeddings gained interest from a 1988 result of <a href="/facts/Nati_Linial/YDkX3Dyk">Nati Linial</a>, <a href="/facts/L%25C3%25A1szl%25C3%25B3_Lov%25C3%25A1sz/X0VB38Ee">László Lovász</a>, and <a href="/facts/Avi_Wigderson/CVHaUAdI">Avi Wigderson</a> that a graph is <a href="/facts/K-vertex-connected_graph/EST9uf8W">k-vertex-connected</a> if and only if it has a 
 
 
 
 (
 k
 −
 1
 )
 
 
 {\displaystyle (k-1)}
 
-dimensional convex 
 
 
 
 S
 
 
 {\displaystyle S}
 
-embedding in general position, for some 
 
 
 
 S
 
 
 {\displaystyle S}
 
 of 
 
 
 
 k
 
 
 {\displaystyle k}
 
 of its vertices, and that if it is k-vertex-connected then such an embedding can be constructed in <a href="/facts/Polynomial_time/77T62gmf">polynomial time</a> by choosing 
 
 
 
 S
 
 
 {\displaystyle S}
 
 to be any subset of 
 
 
 
 k
 
 
 {\displaystyle k}
 
 vertices, and solving Tutte's system of linear equations.
One-dimensional convex embeddings (in general position), for a specified set of two vertices, are equivalent to <a href="/facts/Bipolar_orientation/TSb4PyzJ">bipolar orientations</a> of the given graph.

Convex embedding open-in-new

Convex embedding