geometric graph theory Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geome ...

, a convex embedding of a graph is an embedding of the graph into a

Euclidean space Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...

, with its vertices represented as points and its edges as

line segment In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...

s, so that all of the vertices outside a specified subset belong to the convex hull of their neighbors. More precisely, if

X

is a subset of the vertices of the graph, then a convex

X

-embedding embeds the graph in such a way that every vertex either belongs to

X

or is placed within the convex hull of its neighbors. A convex embedding into

d

-dimensional Euclidean space is said to be in

general position In algebraic geometry and computational geometry, general position is a notion of genericity for a set of points, or other geometric objects. It means the ''general case'' situation, as opposed to some more special or coincidental cases that are ...

if every subset

S

of its vertices spans a subspace of dimension

\min(d,, S, -1)

. Convex embeddings were introduced by

W. T. Tutte William Thomas Tutte OC FRS FRSC (; 14 May 1917 – 2 May 2002) was an English and Canadian codebreaker and mathematician. During the Second World War, he made a brilliant and fundamental advance in cryptanalysis of the Lorenz cipher, a major ...

in 1963. Tutte showed that if the outer face

F

of a

planar graph In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cro ...

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

-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 László Lovász (; born March 9, 1948) is a Hungarian mathematician and professor emeritus at Eötvös Loránd University, best known for his work in combinatorics, for which he was awarded the 2021 Abel Prize jointly with Avi Wigderson. He wa ...

, and

Avi Wigderson Avi Wigderson ( he, אבי ויגדרזון; born 9 September 1956) is an Israeli mathematician and computer scientist. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jerse ...

that a graph is -vertex-connected if and only if it has a

(k-1)

-dimensional convex

S

-embedding in general position, for some

S

k

of its vertices, and that if it is -vertex-connected then such an embedding can be constructed in

polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

by choosing

S

to be any subset of

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

{{reflist, refs= {{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 {{citation , last = Tutte , first = W. T. , authorlink = W. T. Tutte , title = How to draw a graph , journal = Proceedings of the London Mathematical Society , volume = 13 , year = 1963 , pages = 743–767 , mr = 0158387 , doi = 10.1112/plms/s3-13.1.743. Geometric graph theory