All Questions
Tagged with embeddings graph-theory
23 questions
1
vote
0
answers
77
views
Is there a variant of the crossing lemma for multigraphs with arbitrary embedding?
Suppose $G$ is a graph embedded in the plane with $m=|E(G)|$ edges and $n=|V(G)|$ vertices.
Suppose $\operatorname{sim}(G)$, the simplification of $G$ contains $ m' \gg 3n $ edges.
Call the set of ...
- 111
5
votes
0
answers
198
views
"separators" for nonplanar graphs embedded in the plane
Given a nonplanar graph $G$ drawn in the plane with crossings.
Does there exist a small ($o(|V(G)|$) subset $S$ of edges of $G$ such that after the removal of all edges that intersect or share an ...
- 111
1
vote
0
answers
125
views
Do cycle graphs embed isometrically in spheres?
I recently came across, what seems to be a folklore. Namely, that cycle graphs embeds isometrically into spheres $S^n(r)$, for some $n\in \mathbb{N}_+$ and some $r>0$. However, I could not track ...
- 169
4
votes
2
answers
374
views
Knot theory in handlebodies of arbitrary genus
It is well known that not all graphs embed on the plane (e.g. the graph $K_{3,3}$). However, every finite graph embeds into a surface of some genus. One can think of this procedure as starting with a ...
4
votes
0
answers
65
views
Which cellular embeddings of Eulerian graphs have bipartite duals?
It is well-known that a plane graph $G$ is Eulerian if and only if its (geometric) dual $G^*$ is bipartite.
I am interested in generalisations of this result to cellular embeddings of Eulerian graphs ...
- 191
2
votes
1
answer
113
views
Completing a tree to a 2-connected outerplanar graph
Let $T$ be a given (finite) tree.
Question 1: Is it always possible to add edges to $T$ to obtain a $2$-connected outerplanar supergraph $G$?
Question 2: If the answer to Question #1 is negative, can ...
- 6,962
1
vote
0
answers
31
views
Separability of graph component embeddings
I have an undirected graph. I also have an embedding of the graph in $\mathbb{R}^3$. Assume that the graph has 2 connected components. I want to know whether there exists a plane (or better - any ...
- 283
1
vote
1
answer
83
views
Finite graph not embeddable in $H(n,2)$
Let $n\in\mathbb{N}$ and consider $x,y \in\{0,1\}^n$. The Hamming distance of $x,y$ is defined by $$d_H(x,y) = |\{i\in \{0,\ldots, n-1\}:x_i\neq y_i\}|.$$
For $n\geq 2$ let $H(n,2)$ be the graph given ...
- 48.9k
4
votes
3
answers
430
views
How to show that random graphs cannot be embedded with short edges
For each (not necessarily planar) embedding of a graph in $\mathbb{R}^k$ one can calculate the ratio
$$\gamma = \frac{\textsf{mean Euclidean length of edges}}{\textsf{mean Euclidean distance between ...
- 9,720
0
votes
0
answers
377
views
Examples of (infinite) graphs which cannot be embedded into 3d space?
I was thinking about the concept of embedding graphs into Euclidean spaces. Specifically, i was looking for examples of infinite graphs which cannot be embedded in $\mathbb{R}^3$ but can be embedded ...
- 11
1
vote
0
answers
109
views
What is known about this generalization of planar dual?
So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...
- 461
1
vote
1
answer
393
views
Hyperbolic embedding of a directed acyclic graph defined over strings
For integer $n$ and alphabet $\Sigma$ we construct a DAG (directed acyclic graph) $G=(V,E)$ over strings $s\in\Sigma^\star$ as follows:
$$V = \{s\in\Sigma^\star\colon |s|\le n\}$$
$$E = \{(s_1,s_2)\...
- 187
1
vote
0
answers
159
views
Max-min genus of a bipartite graph
As usual, the genus of a graph with a prescribed circular ordering of the edges at each vertex is defined as the minimum genus of an orientable surface in which the graph can be drawn without edge ...
- 1,389
1
vote
1
answer
116
views
On graph imbedding genus clarification
Given a graph the minimum genus $g$ is the minimum number of handles needed so that there an imbedding of the graph on the surface with no edge crossings.
If the graph is of genus $g$ then is there ...
- 13.9k
4
votes
2
answers
232
views
Number of non-equivalent graph embeddings
Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings.
Is there a way ...
- 13.9k
2
votes
1
answer
137
views
VLSI circuit embeddings
In the following paper by Valiant
http://www.computer.org/csdl/trans/tc/1981/02/06312176.pdf
He shows under theorem 2 (at the bottom of the second page) that any planar graph $G$ of degree 3 or 4 ...
- 903
4
votes
1
answer
700
views
Embedding graphs into hyperbolic spaces
Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...
- 617
10
votes
1
answer
403
views
Are there non-trivial graphs that uniquely embed to hypercubes?
The $n$-dimensional hypercube is the graph formed by $0$-$1$ sequences of length $n$ where two vertices are adjacent if they differ at only one place.
The weight of a sequence is the number of $1$'s ...
- 18.8k
7
votes
2
answers
379
views
Number of edges in linklessly embeddable graphs
What is the maximum number of edges of an $n$-vertex linklessly embeddable graph?
A more general question is the following. What is the maximum number of edges of an $n$-vertex graph with Colin de ...
- 93
2
votes
0
answers
139
views
Disks in Flat Embeddings of Graphs in $\mathbb{R}^3$
Robertson, Seymour and Thomas proved that any linkless graph $G$ has a flat embedding in $\mathbb{R}^3$ (see for example A survey of linkless embeddings). An embedding of $G$ is flat if for any cycle $...
- 415
3
votes
0
answers
177
views
Different definitions of linkless graphs
Robertson, Seymour and Thomas defined linkless embeddings of graphs as follows:
An embedding of $G$ is linkless if every pair of disjoint circuits of $G$ have zero linking number (see here). However ...
- 415
1
vote
1
answer
451
views
Difference between straight and piecewise linear and continuous embeddings of graphs / complexes in d-dimensional space?
Here is my main question: what is the difference between "straight" and "piecewise linear" and "continuous" embeddings of graphs/complexes in d-dimensional space?
Moreover I would like to know if any ...
- 415
14
votes
0
answers
416
views
Monotone embedding of complete binary tree in hypercube
Embedding different graphs, especially binary trees, in the hypercube has a huge literature. However, I could not find anything if we restrict the embedding to be monotone. So I would like to ...
- 18.8k