• Source: 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 the convex hull 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 general position 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 W. T. Tutte in 1963. Tutte showed that if the outer face



F


{\displaystyle F}

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



F


{\displaystyle F}

-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.
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



(
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 polynomial time 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 bipolar orientations of the given graph.




References

Kata Kunci Pencarian:

• Ruang vektor topologis
• Convex embedding
• Planar graph
• Tutte embedding
• Nash embedding theorems
• Locally convex topological vector space
• Polyhedron
• Convex drawing
• Nonlinear dimensionality reduction
• Toric variety
• Topological vector space