10
This question is incomplete without specifying what information about the graph as it changes you want your dynamic graph data structure to output or support queries for. But the following paper is likely relevant, even though it is described in a more general setting of combinatorial embeddings in arbitrary genus rather than just planar. It definitely ...
8
Embedding planar graphs (with max degree four) in an adjacency-preserving way onto a grid is NP-complete, meaning that there's unlikely to be simple necessary and sufficient conditions. Actually that's still true even for embedding trees into a grid. See:
S. Bhatt and S. Cosmodakis. The complexity of minimizing wire lengths in VLSI layouts.
Inform. Proc. ...
8
Oh oh. You want to be very very careful. Contact graphs of convex polytopes in 3d can realize any graph. Surprisingly, the clique can be realized by n polytopes that are n rotated and translated copies of the same polytope (the mind boggles). See this paper:
http://www.cs.uiuc.edu/~jeffe/pubs/crum.html
This already implies that you can encode pretty nasty ...
7
As a first remark, your focus seems to be on hypergraphs but I think that most of the literature about embedding hypergraphs prefers to work with simplicial complexes. A good reference on these questions is this paper by Matousek, Tancer and Wagner.
Does Fáry's Theorem hold in higher dimension?
The answer is no.
There are actually 3 different notions ...
7
Suresh asked me to assemble my comments above into an answer, so here it is. I'm not really sure it's an answer to the original question, though, since it's not obvious how to make it polynomial time when the dimension of the input Euclidean space is non-constant. It does at least have the advantage of avoiding any problem with large $1/\epsilon$ as the ...
4
Schnyder Theorem states that a graph is planar iff its incidence poset has dimension at most 3. This has been extended by Mendez to arbitrary simplicial complexes (see "Geometric Realization of Simplicial Complexes", Graph Drawing 1999: 323-332). Strangely enough there is a much older paper with a very similar title "The geometric realization of a semi-...
4
If I understand your problem correctly, it seems like you're looking to examine a furthest-point weighted Voronoi diagram under the Manhattan ($\ell_1$) distance. The transformation is as follows.
For each point $p_i$ on the grid, define the distance function $$d_i(x) = \max(0, \|x - p_i\|_1 - (t_{n+1}-t_i))$$ Then $d_i(x)$ is the (truncated) distance of $...
4
The distortion of embedding any $n$-point metric in ultrametric is at most $n-1$, and on the other hand, the distortion of embedding the path metric $P_n$ in ultrametric is at least $n-1$.
Similarly, if you are interested in probabilistic embedding, then by Fakcharoenphol, Rao, and Talwar result mentioned above, any $n$-point metric space probabilistically ...
4
Your construction does not work in general for the value of $k$ given.
Say $x = 0$ and $y= (1, 0, \ldots, 0)$ (or any other standard basis vector). Then $f(x) = 0$ and $HDy$ is a vector with $1 + \log_2 d$ nonzero entries. We have
$$
Pr[f(y) = 0] = \left(1 - \frac{1 + \log_2 d}{d}\right)^k \approx 1-O\left(\frac{k\log d}{d}\right),
$$
for $k \ll d$. Of ...
3
Very important property : tree-width duality.
e.g look at :
Tree-width of hyper-graphs and surface duality
by Frederic Mazoit,
The abstract is as follow:
In Graph Minors III, Robertson and Seymour write: "It seems that the
tree- width of a planar graph and the tree-width of its geometric dual
are approximately equal, indeed, we have convinced ...
3
There is a classic result by Fakcharoenphol, Rao, and Talwar showing that any $n$ point metric space can be embedded into an HST metric with expected distortion $O(log\, n)$.
One should keep in mind that this result holds only for probabilistic embeddings, since there are metrics (such as the $n$-cycle) which will give you an $\Omega(n)$ distortion if you ...
3
To keep things a little cleaner let's assume that the graph has a Hamiltonian cycle that's embedded along the spine so that each cell of the embedding lives within a single page. Also those spine edges are places where multiple cells meet so let's make them vertices as well.
Then, within each page of the book, the dual graph is a forest, with all vertices ...
2
I don't think we can get any property close to dual's properties in planar graphs, e.g Babai show that every graph can be embedded in a book with three pages (see Archdeacon's survey Theorem 5.1), so if $p$ is a duality property for books with three pages then $p$ holds for general graphs.
2
It's not "obtained", but rather the bound the authors want on $\mathrm{Prob}[|u_1|\ge s]$. The Chernoff inequality says how large $s$ needs to be in order to guarantee the desired upper bound. As they assume $d \le n$, it suffices for $s$ to satisfy $s^2 \cdot d/2≥\ln(20n^2)$, which leads to $s=c\cdot d^{-1/2} \sqrt{\log n}$ for some appropriately chosen ...
2
Every $\epsilon$-biased set gives a code whose minimal relative distance is $0.5 - \epsilon$ and maximal relative distance is $0.5 + \epsilon$.
To see it, write the elements of the set as the rows of a matrix, and then define the code to be the span of the columns of the matrix. The $\epsilon$-biased property of the set is equivalent to saying that the ...
1
I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is "Learning a kernel matrix for nonlinear dimensionality reduction" by Weinberger, Sha, and Saul if I am not ...
Only top voted, non community-wiki answers of a minimum length are eligible
