## Invited Session Wed.2.H 2036

#### Wednesday, 13:15 - 14:45 h, Room: H 2036

**Cluster 4: Conic programming** [...]

### Semidefinite programming and geometric representations of graphs

**Chair: Monique Laurent and Christoph Helmberg**

**Wednesday, 13:15 - 13:40 h, Room: H 2036, Talk 1**

**Susanna Reiss**

Optimizing extremal eigenvalues of the weighted Laplacian of a graph

**Coauthors: Frank Göring, Christoph Helmberg**

**Abstract:**

We study connections between the eigenspaces of the graph's Laplacian and graph properties. For this purpose, we analyze optimal solutions of *min*_{w}{ λ _{max}(L_{w}(G))- λ _{2}(L_{w}(G))}, by semidefinite programming techniques, i.e., we optimize nonnegative edge weights *w* of a graph, that sum up to one, so as to minimize the difference of the maximum and the second smallest eigenvalue of the corresponding weighted Laplacian *L*_{w}(G). The dual program may be interpreted as a graph realization problem in Euclidean space, that reflects the optimized eigenspaces. We present connections between structural properties of the graph (especially its separator structure) and geometrical properties of optimal graph realizations, thereby shedding light on relations between the graph's properties and its eigenvectors. Furthermore we are able to prove the existence of optimal graph realizations whose dimensions are bounded by the tree-width of the graph plus one.

**Wednesday, 13:45 - 14:10 h, Room: H 2036, Talk 2**

**Marcel Kenji de Carli Silva**

Optimization problems over unit-distance representations of graphs

**Coauthor: Levent Tuncel**

**Abstract:**

We start with a result of Lovász relating the theta number of a graph to its smallest radius hypersphere embedding where each edge has unit length. We use this identity and its generalizations to establish close relationships among many related graph parameters. We then study the more general problem of finding the smallest radius of an ellipsoid of a given shape that contains an embedding of a given graph where each edge has unit length.

This talk is based on joint work with Levent Tunçel.

**Wednesday, 14:15 - 14:40 h, Room: H 2036, Talk 3**

**Antonios Varvitsiotis**

Two new graph parameters related to semidefinite programming with a rank constraint

**Coauthors: Marianna Eisenberg-Nagy, Monique Laurent**

**Abstract:**

We consider geometric representations of edge weighted graphs

obtained by assigning unit vectors to the nodes, such that the

weight of each edge is equal to the inner product of the vectors

assigned to its endpoints. We introduce two new graph parameters

related to the minimum dimension where such representations exist.

Their study is motivated by their relevance to bounded rank

positive semidefinite matrix completions and to the graphical

Grothendieck problem with a rank constraint.

In this talk we analyze combinatorial and geometric properties of

these parameters.

In particular, we provide forbidden minor characterizations as well

as structural and complexity results. Additionally, we discuss how

our results imply some known characterizations of parameters

related to Euclidean graph realizations and Colin de

Verdière-type graph invariants.