Let $P$ be a polytope given by a vertex description, i.e., $P=conv(\{x_1,\ldots,x_m\})\subset\mathbb{R}^n$.

Is there an efficient (i.e., not relying on Linear Programming) algorithm to compute the edge skeleton of $P$ ?

More generally, given a polytope $P=conv(\{x_1,\ldots,x_m\})$ AND its edge skeleton $ES=\{(i,j): (x_i,x_j) \text{ is an edge of } P\}$, is there an efficient algorithm to update the skeleton after insertion of a new vertex $x_{m+1}$, i.e., to identify the subset of vertices $I\subseteq\{1,\ldots,m\}$ such that $x_i,x_{m+1}$ is an edge of $conv(P,x_{m+1})$ ?

This problem can easily be solved by LP: Given two vertices $x_i,x_j$ , one can test if the mid-point $(x_i+x_j)/2$ can be expressed as a convex combination involving the point $x_k$ (with a positive weight), for each $k\notin\{i,j\}$. However, this naive approach seems to be highly nonefficient, as it involves solving $(m-2)$ LPs to test for the membership $(i,j)\in ES$...

I found a recent related paper https://arxiv.org/abs/1412.3987 that does the job when $P$ is given by an optimization oracle and a superset of vertex directions, but this seems to be a more complicated setup than a vertex description, and it also relies on linear programming.