0
votes
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
2answers
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
0answers
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
1answer
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
0answers
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
3answers
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
1answer
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
1answer
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
1answer
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
0answers
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
1answer
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
3answers
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
1answer
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
1answer
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
3answers
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
4answers
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 ...