# Tagged Questions

**1**

vote

**0**answers

73 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 ...

**3**

votes

**0**answers

60 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 ...

**1**

vote

**1**answer

93 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 ...

**0**

votes

**0**answers

68 views

### Existence of a sequence of (almost) Moore irregular graphs embedded on closed surfaces

Let $S_{g}$ denote the genus $g$ closed orientable surface. I'm interested in disproving the existence of a certain configuration of simple closed curves on $S_{g}$. I'd be happy to go into more ...

**1**

vote

**1**answer

180 views

### Counting edges in embeddable CW-complexes in R^3

Using Euler's formula ($V-E+F = 2$ where $V$, $E$ and $F$ are the number of vertices, edges and faces), we can easily count the number of edges in maximal graphs that are embeddable in plane: 3n-6. I ...

**2**

votes

**0**answers

52 views

### Minimal set of 2-2 Pachner move null sequences on a (nonplanar) trivalent graph?

A "null sequence" is of course a sequence of Pachner moves (inside a closed
area) that doesn't change the trivalent graph. E.g. doing the same Pachner move
twice (leads to orthogonality of 6j symbols) ...

**1**

vote

**1**answer

166 views

### 3-complexes not embeddable in 3-space

My question is about embeddability of 3-dimensional complexes in R^3. Do we have something like Kuratowski's theorem for complexes in 3-space which specifies a set of minors for non-embeddability?

**2**

votes

**1**answer

730 views

### What is a good algorithm to measure similarity between two dynamic graphs?

I am using graphs to represent structure present in a scene. The vertices represent the objects in the scene and the edges represent the relationship between two nodes(touching, overlapping, none). ...

**4**

votes

**2**answers

194 views

### A question about trees and planar graphs

Let T be a tree which satisfies the following conditions. (A) The set of vertices of T is denumerably infinite. (B) Each vertex of T is an end-point of at most finitely many edges of T. Does there ...

**2**

votes

**0**answers

89 views

### Reachability in dynamic random graphs

There has been some advice on how to ask questions. So I reask my question.I have a problem related to graph theory, random graphs or random geometric graphs in special that really confuses me. ...

**6**

votes

**1**answer

271 views

### embeddings of graphs into surfaces

There is a vast literature on embeddings of graphs into surfaces.
I am interested in embeddings of graphs that
belong to the given homotopy class. Here is the precise formulation.
I have two ...

**0**

votes

**0**answers

65 views

### A sufficient condition for attaching squares to a 1 skeleton so that the CW-complex is a 2 - manifold

Suppose we have a finite connected graph $G$, I want to add 2 -cells to $G$ so that the 2 cells have boundaries of length 4 (squares) and so that $G$ is the 1 skeleton of a surface (2-manifold) ...

**1**

vote

**3**answers

284 views

### If a graph embeds in the projective plane or the torus is there a bound on the number of edge crossings it has in the plane?

If a graph embeds in the torus or the projective plane is there an upper bound on the number of edge crossings it has in the plane?

**7**

votes

**1**answer

247 views

### How large is this “algebra” of defining graphs for Right-angled Artin groups?

As part of my research, I have been trying to construct a spherical space at infinity for every right-angled artin group. I've been able to work it out for a certain class of defining graphs. I'd like ...

**3**

votes

**1**answer

185 views

### Convex polyhedral decomposition of spheres

Is there a decomposition of $S^2$ into $k$ (geodesically) convex polyhedra that are congruent to each other? What about $S^n$ for $n>1$?
Remarks:
A polyhedron is defined as an area enclosed by a ...

**3**

votes

**1**answer

414 views

### Klein Bottle exception to the Heawood Conjecture [duplicate]

Possible Duplicate:
The Klein bottle and the Heawood Conjecture
It is well known that the Heawood Conjecture states that the bound for the number of colours which are sufficient to colour a ...

**11**

votes

**0**answers

697 views

### Hamiltonian cycles and fundamental groups

I'm interested in the interplay between the Hamiltonian cycles of graphs and the compact surfaces they embed in. I was doing some reading on the Lovász conjecture for Cayley graphs, I started noticing ...

**6**

votes

**1**answer

449 views

### Local complementation group of simple graphs

This is my first time posting a question, so please excuse me for any incomplete or confusing descriptions.
Let's assume we start with one simple graph(no multi-edges and no loops of a vertex to ...

**18**

votes

**3**answers

694 views

### Drawing planar graphs with integer edge lengths

It is well known that every planar graph has an embedding such that every edge is drawn as a straight line segment (Fáry's Theorem). Kemnitz and Harborth made the following stronger conjecture
...

**2**

votes

**1**answer

314 views

### When are nontopological bistellar flips manifold-preserving?

A topological bistellar flip is the term used by Dougherty, Faber, and Murphy to describe a bistellar flip that does not cause any face of a complex to be duplicated. Suppose we consider a ...

**7**

votes

**1**answer

833 views

### Beyond an intro to topological graph theory…

I'm looking to find out what active areas of research there are in topological graph theory, particularly those that interface strongly with other areas of math (say, group theory, algebraic topology, ...

**7**

votes

**3**answers

293 views

### Why are some tilings introduced as geometrical objects, not graphs?

Let's say you have a planar tiling. Quite often these tilings are introduced as geometrical objects with metrics; each tile having coordinates assigned to its vertices.
The tiling has an associated ...

**-6**

votes

**4**answers

563 views

### What is the max number of points in R^3, interconnected by generic curves?

The largest complete graph that embeds in 2 dimensions is $K_4$, while the largest complete graph that embeds in 3 dimensions is $K_{\infty}$, right? However, I don't know any constructive proof of ...