EUDML

Let $G = (V, E)$ be a 3-connected planar graph, with $V = {1, ..., n}$ . Let $M = (m_{i, j})$ be a symmetric $n \times n$ matrix with exactly one negative eigenvalue (of multiplicity 1), such that for $i, j$ with $i \neq j$ , if $i$ and $j$ are adjacent then $m_{i, j} < 0$ and if $i$ and $j$ are nonadjacent then $m_{i, j} = 0$ , and such that $M$ has rank $n - 3$ . Then the null space $ker M$ of $M$ gives an embedding of $G$ in $S^{2}$ as follows: let ${a, b, c}$ be a basis of $ker M$ , and for $i \in V$ let $ϕ (i) : = (a_{i}, b_{i}, c_{i})^{T}$ ; then $ϕ (i) \neq 0$ , and $ψ (i) : = ϕ (i) / ∥ ϕ (i) ∥$ embeds $V$ in $S^{2}$ such that connecting, for any two adjacent vertices $i, j$ , the points $ψ (i)$ and $ψ (j)$ by a shortest geodesic on $S^{2}$ , gives...

Geometric algorithms and combinatorial optimization

Martin Grötschel; László Lovász; Alexander Schrijver — 1988

Geometric algorithms and combinatorial optimization

Martin Grötschel; László Lovász; Alexander Schrijver — 1988

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 9 of 9

Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture.

Selected topics of matroid theory and its applications

Exact mixing in an unknown Markov chain.

Semidefinite functions on categories.

Nový pohled na algoritmickou matematiku

Je nový algoritmus lineárního programování lepší nebo horší než simplexová metoda?

On the null space of a Colin de Verdière matrix

Geometric algorithms and combinatorial optimization

Geometric algorithms and combinatorial optimization