# Questions tagged [topological-graph-theory]

Graph theoretical questions with a topological flavour. For example, graphs on surfaces, spatial embeddings, and geometric graphs. Use the graph-drawing tag for questions specific to graph drawing (e.g. crossing numbers).

51 questions
Filter by
Sorted by
Tagged with
44 views

So it is well known that given a planar graph, $G$, embedded in the plane (without edge crossing, so a planar embedding). One can construct the planar dual, $G^*$. What is perhaps slightly less well-...
424 views

### Doubly periodic 4 color theorem?

Let $G$ be a graph embedded (without crossings) on a torus $T$. It's fairly well known that this implies the chromatic number of $G$ is at most 7. If I lift $G$ to the universal cover of $T$, we get a ...
62 views

182 views

117 views

### Computing with Graphs in Surfaces

I asked this question yesterday on math.stackexchange, but the only response so far hasn't really addressed the question, so I thought I'd cross-post it. I am currently working on a research project ...
8k views

### Graduate Schools for Graph Theory [closed]

I am a rising senior in a small liberal arts college, and I was wondering if anyone could suggest me good graduate schools for graph theory. My only exposure to graph theory has been the intro graph ...
941 views

### Spanning trees of plane graphs containing an edge of every face

I feel sure this must be known, but can I find it?? Which connected plane graphs (graphs drawn in the plane without crossings) have a spanning tree such that at least one edge of each face is in the ...
198 views

### Polyhedral embeddings of large face-width where all faces have the same length

Where can I find examples of polyhedral embeddings of simple graph with large face-width, such that all the faces have the same length? By polyhedral embedding I mean an embedding of the graph on a ...
230 views

### Maximum fixed genus Bipartite graphs

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with $n$ vertices of color $1$ and with $n$ vertices of color $2$. What is the maximum number of edges that a genus $g$ graph $B_{n,n}$ can have? ...
375 views

### Obstructions to genus $g+1$ bipartite graph having genus $g$

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices. Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...
412 views

### Flow on Infinite Graphs

Assume you have a simple, infinite graph $G$ with bounded degree (there is an upper bound for the degree of the nodes). Choose an arbitrary vertex $x\in V(G)$ and consider  G_{n}:=\{x\in G:d(x_0,x)\...
550 views

### Can we map every graph in the plane such that all induced cycles selfintersect?

Suppose we have a graph G. Is it true that we can map its vertices to the plane such that when connecting neighboring vertices with segments, then any induced cycle of G that has length at least 4 ...
331 views

### Spectral techniques for genus of a graph

A generic question: are there any spectral techniques to estimate the genus of a graph? I am interested in complete balance multipartite graph.
1k 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 ...
267 views

### Why are graph imbeddings defined the way they are?

In my recent question I asked about a proof for the fact that the dual of a dual graph imbedding is equal to the original graph. Thinking about this a little more leads me to wonder why graph ...
211 views

### Double duality for “geometrically defined” graph imbeddings

I am studying imbeddings of (connected, undirected, unweighted, multi-)graphs on oriented surfaces of arbitrary genus, and I am searching for a reference for the statement that the dual of the dual ...
1k views

### Obstructions for embedding a graph on a surface of genus g

Kuratowski's theorem tells us the complete graph $K_5$ and the bipartite graph $K_{3,3}$ are the only obstructions to a graph being planar, ie embeddable in the plane with no edge-crossings. Is the ...
627 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 ...
1k views

### Given a graph embedded on a torus, how many edges are necessary for noncontractible loops to be long?

If we are given a graph embedded on a torus, with the following properties, what is the minimum number of edges it can have? Any noncontractible loop is comprised of at least n edges. Any ...
3k views

### Singular homology of a graph.

By a graph I will understand an undirected graph without multiple edges or loops. By a morphism of graphs I will understand a map $f$ between the underlying sets of vertices, such that if $x$ and $y$ ...
9k views

### Reporting all faces in a planar graph

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...
1k views

### Simplicial Representations of (Hyper)Graph Complexes

For graph complexes, which are families of graph [on a fixed number of vertices n] closed under the deletion of edges, there is a natural simplicial complex capturing that information. Specifically, ...
1k views

### Is there a bipartite analog of graph theory?

I would like to compile a list of questions about graphs that have a non-trivial analogs for bipartite graphs. Let me give the following examples: Cycle vs Even cycle. Most questions about cycles in ...