1
vote
2answers
122 views

TSP, but for all routes not all points

Hello I am trying to solve a problem involving a cross-country ski trail map. I wish to travel every trail on the map, at least once, but no more than twice (so I can out-and-back on a destination, ...
8
votes
2answers
338 views

Is there an analog of 'Directed Graph' for topological spaces?

In a directed graph, certain paths are distinguished: Those that follow the edge direction on each edge. I was wondering if one could (or does) formulate a notion of a 'Directed Topological Space', on ...
7
votes
2answers
235 views

Higher-dimensional Fáry's theorem?

Fáry's theorem says that every finite simple planar graph admits a planar embedding with straight line edges. For which $(k,d)$ is it true that every finite $k$-dimensional simplicial complex ...
26
votes
1answer
1k views

Does this knot invariant distinguish trefoil chiralities?

Let $C_N$ denote the labelled configuration of $N^{th}$ roots of unity with $p_J = e^{\frac{2\pi iJ}{N}}$ for $J = 1\ldots N$. As a corollary of something else I was playing around with, I recently ...
2
votes
0answers
86 views

Graphs, non-Hausdorfness and Wallman compactifications of non-regular spaces

Given a non-Hausdorff space $X$, one can form a graph $G_X$: vertices the points of $X$, edges indicating point pairs not separated by open sets. Up to graph-theoretically (but not topologically) ...
3
votes
1answer
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 ...
36
votes
8answers
4k views

What is a continuous path?

I would like some help, because I am getting mad trying to answer the following Question: Let $X$ be a topological space, what is a continuous path in $X$? Well, maybe you're getting nervous ...
0
votes
1answer
230 views

“Skein” equations sets that can reduce any graph

Consider for example the approach to the Kuperberg G2 or the Yamada polynomial. I don't know whether relations of graph (in contrast to knot) theory are also usually called "skein" but I simply carry ...
2
votes
2answers
995 views

How many lanes has a freeway? (Crossing free Kuperberg G2, that is.) EDITED

For referencing, I keep the original title and post and ask only about the simplest case (and forget the freeway with crossings for now). Consider a trivalent graph, e.g. the dodecahedron or cube ...
1
vote
1answer
715 views

Representations of regular maps (four color theorem)

For the scope of the four color problem and without lack of generality, maps can be represented in different ways. This is generally done to have a different perspective on the problem. For example, ...
4
votes
2answers
458 views

Is there a formula to count how many different topological regular maps can be created with n faces (on a sphere)?

Notes: For "regular" I intend maps in which the boundaries form a 3-regular planar graph For "different" I intend maps that cannot be topologically transformed one into another (faces ...
1
vote
1answer
256 views

Winding number bijection on graphs

Let $G=(V,E)$ be an isoradial graph. In other words the graph can be imbedded into the plane such that each face (plaquette) can be circumscribed a circle of radius 1 with the circle's center ...
6
votes
6answers
1k views

Elegant representations of graphs in R^3

If I have a graph of a reasonable size (e.g. ~100 nodes, ~40 edges coming out of each node) and I want to represent it in R^3 (i.e. map each node to a point in R^3 and draw a straight line between any ...
13
votes
2answers
647 views

The Klein bottle and the Heawood Conjecture

Let $\Sigma_g$ be a surface of genus $g$. The Heawood Conjecture gives a closed formula in one variable, $\chi$ (the Euler characterstic of $\Sigma_g$), for the minimal number of of colors needed to ...
11
votes
1answer
437 views

Homotopy theory for spanning trees of a graph

I am studying a paper of L. Lovász, ``A homology theory for spanning trees of a graph,'' but professor Babai has told me that Lovász later realized that this work is better framed in the language of ...
8
votes
2answers
1k views

How many simply connected subsets of an n-by-m grid?

Given an n-by-m square grid graph, how many ways are there to choose a subset of the vertices which is simply connected? Here, a subset of vertices is simply connected if the vertices, together with ...
9
votes
2answers
632 views

Is there a way to see a topological group as the “Cayley graph” of its “infinitesimal generators”?

At the time of writing, the most recent blog post over at What's new by Terrence Tao is Cayley graphs and the geometry of groups, and that (excellent, as with most of Tao's writing) post most ...
1
vote
2answers
1k views

Maximum number of shortest-paths

I would like to know if there is a equation for the maximum number of shortest paths that pass through r where r is a node contained in any path from node s (a fixed node, i mean, s is the only source ...
-6
votes
4answers
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 ...
2
votes
4answers
9k views

Difference between connected vs strongly connected vs complete graphs [closed]

What is the difference between connected strongly-connected and complete? My understanding is: connected: you can get to every vertex from every other vertex. strongly connected: every vertex ...
9
votes
3answers
311 views

Groupoid of moves on trivalent fatgraph

Let $T$ be a finite trivalent fatgraph - i.e. a graph with a cyclic order of the edges at each vertex. Then there are certain basic "moves" we can perform on $T$: an embedded edge can be collapsed and ...
4
votes
5answers
925 views

A walk on a compact 2D surface embedded in 3-space that never returns home

At the risk of asking an uninformed question... Imagine an ant on a compact two-dimensional surface embedded in 3-space. The ant is placed at a point on the surface with random orientation. Once ...