# Tagged Questions

**5**

votes

**2**answers

197 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**4**

votes

**1**answer

97 views

### genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each ...

**2**

votes

**4**answers

1k views

### Graduate Schools for Graph Theory

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

**8**

votes

**2**answers

425 views

### spanning trees of plane graphs

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

**2**

votes

**0**answers

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

**2**

votes

**1**answer

175 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? ...

**2**

votes

**1**answer

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

**9**

votes

**1**answer

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

**12**

votes

**3**answers

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

**13**

votes

**2**answers

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

**18**

votes

**3**answers

721 views

### Obstructions for planar graphs on surfaces of genus g

Kurotowski'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 ...

**11**

votes

**1**answer

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

**11**

votes

**2**answers

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

**4**

votes

**2**answers

2k 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$ ...

**4**

votes

**2**answers

3k 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 ...

**6**

votes

**0**answers

698 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, ...

**3**

votes

**3**answers

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

**3**

votes

**1**answer

1k views

### ? A graph is four colorable if and only if it is planar.

? A graph is four colorable if and only if it is planar.
Is this true, I know that if a graph is planar it is four colorable, but is it true that if a graph is four colorable it must be a planar ...

**1**

vote

**2**answers

463 views

### How many dimensions I need to embed a graph? [duplicate]

Possible Duplicate:
What is the max number of points in R^3, interconnected by generic curves?
Given a set of points connected by edges lying on an euclidean plane,
I'd like to find which is ...

**26**

votes

**3**answers

4k views

### Why are planar graphs so exceptional?

As compared to classes of graphs embeddable in other surfaces.
Some ways in which they're exceptional:
Mac Lane's and Whitney's criteria are algebraic characterizations of planar graphs. (Well, ...