# Tag Info

Accepted

### Can all crossings in a graph be moved to one point?

No, this is not always possible. Lemma. Let $G$ be an $n$-vertex graph with at least $3n-2$ edges. Then $G$ cannot be drawn in the plane so that all crossings occur at the same point. Proof. We make ...
• 31.8k

### Doubly periodic 4 color theorem?

As Michael Klug points out in the comments, I've thought about related questions before. I'll make a few comments on the question. Firstly, the usual reduction allows one to consider triangulations ...
• 68.1k
Accepted

### Orientations of Planar Graphs

Such an orientation always exists, here is a proof. Take your 2-edge-connected graph $G$, and consider its dual graph $D$. $D$ has a proper 4-coloring in which each face of $D$ contains at most 3 ...

### Number of non-equivalent graph embeddings

Ad 1. One notion of two embeddings being equivalent is "there exists an ambient isotopy carrying the image of one embedding onto the image of the other". Another, stronger, notion, more usual in the ...
• 6,031
Accepted

### Find all 2-planar drawings of $K_6$ and $K_7$

The list of all good drawings of $K_6$ can be found in the doctoral thesis by Nabil H. Rafla: https://escholarship.mcgill.ca/concern/theses/x346d4920 On pages 164-165 the drawings are described by the ...
• 6,046

### Is there a "simplest" way to embed a graph in 3-space?

I agree with the comments that there will be no simplest embedding in general. Nevertheless in certain cases there are embeddings with nicer properties. One way to embed a simplicial graph (ie no ...
• 68.1k
Accepted

### Is there a "simplest" way to embed a graph in 3-space?

Another way to generate a topologically simple embedding into $\mathbb{R}^3$ is to embed the graph in a surface of minimal genus which in turn embeds into $\mathbb{R}^3$. One can generate the ...
• 687

### Let $G$ be a graph of genus $g$. Is the number of (non necessarily disjoint) 5-clique subgraphs at most $f(g)$ for some function $f$?

Yes, this is true. See my paper Subgraph densities in a surface with Gwenaël Joret and David Wood. We prove that for every $s \geq 5$, the number of $s$-cliques in a graph of Euler genus $g$ is at ...
• 31.8k

Accepted

### Loop of crosscaps and Euler characteristic

The Euler characteristic formula only applies when all the faces are homeomorphic to disks. This is the case in the second picture. However, in the first picture, one of the faces is homeomorphic to ...
• 1,617
Accepted

### Genus for specific family of graphs

Since the genus is additive over connected components, it is sufficient to find $g$ vertex-disjoint subdivisions of $K_{3,3}$, one in each copy of $C_{10}\times C_{10}$. This will show that the genus ...
• 6,046

### Conditions on graphs to assure unique embedding on a fixed genus surface

One condition is that the embedding has "large edge-width," i.e., every noncontractible cycle is longer than every facial walk. Intuitively, I believe that large edge-width can be thought of ...
• 296
Accepted

### Bookthickness of covering space

The graph of the icosahedron is a 2-fold cover of $K_6$; this covering can be induced by the covering of the projective plane by the sphere. The graph of the icosahedron is planar and Hamiltonian, so ...
• 6,046
Accepted

### Bounds on lengths of intervals in bounded-degree interval graphs

Yes, we may take the function to be $2\Delta$. Lemma. Every interval graph $G$ has an interval representation where all intervals have length between $1$ and $2\Delta$, where $\Delta$ is the maximum ...
• 31.8k

• 13.6k
1 vote

### On graph imbedding genus clarification

(Not an answer, yet too long for the comment box, and thought by me to be helpful for the OP) I do not understand even your question 1. I had too hard a time parsing your question 1., which has at ...
• 6,031
1 vote

### Connection between connectivity and cohesion of a graph

A k-connected graph G, k>0, will be (2k+1)-cohesive. However, one can easily construct a (2k+1)-cohesive graph which is only 1-connected: take two disjoint copies of complete graphs and add one edge ...

Only top scored, non community-wiki answers of a minimum length are eligible