# 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

175 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

50 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

161 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

573 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

84 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

267 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

240 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

182 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

404 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

612 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

445 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

684 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

309 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

821 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

288 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

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