# Tagged Questions

**0**

votes

**0**answers

65 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

171 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

46 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) ...

**0**

votes

**1**answer

117 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?

**1**

vote

**0**answers

356 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

193 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

81 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

260 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

279 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

237 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

175 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

386 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

609 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

442 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

666 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

303 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

807 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

284 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

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

**1**

vote

**0**answers

288 views

### What are some special properties of the Euclidean R^3? [closed]

Premise: Any physically possible process of computations requires an underlying physical process. Such physical process can exist only in the available physical space, which can be modeled by the ...