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 …

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 embeddin …

Assume you have a simple, infinite graph with bounded degree (there is an upper bound for the degree of the nodes). Choose $x$ an arbitrary vertex and consider $$ G_{n}:=\{x\in 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- …

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 plana …

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 l …

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 gene …

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 o …

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 …

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 e …

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 wonde …

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

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 ques …

? 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 m …