17
votes

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

10
votes

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

10
votes

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

6
votes

### 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
votes

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
votes

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

5
votes

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

5
votes

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

5
votes

### Do triple-linked graphs exist?

If you restrict to straight-line embeddings (where edges are line segments), then the answer is yes: using the result in Erdos-Szekeres in high dimensions there exists some $n$ such that if you have $...

5
votes

Accepted

### Is this drawing of $K_{4,4}$ knotted?

Here is a proof that all such embeddings are knotless. Consider the four half-planes bounded by $A$ which each contain one of the points $b_i$. Then these planes give an open-book decomposition which ...

5
votes

### Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

I don't know exact genus. I suspect it is 4 but do not have a proof. So I am making this community wiki, maybe somebody can supply this information.
The generating cycles $p$ and $q$ satisfy $(pq)^3=(...

Community wiki

4
votes

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

4
votes

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

4
votes

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

3
votes

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

3
votes

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

3
votes

### Dipping into sets of parallel edges in graph drawings

The following should work: for $uv$ with parallel edges connecting them, consider the union of faces not containing vertices, blow it up slightly if necessary to make it disk-shaped and let $\alpha$, $...

3
votes

Accepted

### Embedding linklessly embeddable graphs without Borromean rings

Isn't it that linklessly and flatly embeddable are the same family, and that a flat embedding can not contain a Borromean ring?
upd - clarification:
From the wiki article on linkless embeddings: "...

3
votes

Accepted

### Positive type function on open subgroup

Note that
$$\phi(g_{j}^{-1}g_i)=1 \Leftrightarrow g_{j}^{-1}g_i \in H$$
On $G$ define $g \equiv h \Leftrightarrow g^{-1}h \in H$.
Now, let $n \in N, c_i \in \mathbb{C}, g_i \in G$.
Split $g_1,.., g_n$ ...

2
votes

### Number of non-equivalent graph embeddings

Peter Heinig's answer is excellent, but here are some further remarks:
Under the "ambient isotopy" definition, there are infinitely many classes of embeddings (because the mapping class group is ...

2
votes

### Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

According to Sagemath documentation, the time complexity of their algorithm is
$$
\mathcal{O}\left(|V| \prod_{v \in V} (d(v) - 1)!\right).
$$
(Note that in this instance this evaluates to $6^{60}$.)
...

1
vote

Accepted

### Bounds on lengths of boxes in bounded-degree box graphs

$\DeclareMathOperator{\cub}{\operatorname{cub}}$$\DeclareMathOperator{\box}{\operatorname{box}}$$\DeclareMathOperator{\diam}{\operatorname{diam}}$I now think that the answer to the second question is ...

1
vote

### 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$?

Say $\gamma(G)$ is the genus of a graph $G$. If $G$ has components $G_1,\dots,G_c$ then $\gamma(G)=\sum_{i=1}^c \gamma(G_i)$. This property is called the additivity of genus (and much stronger results ...

1
vote

### Chromatic numbers of geometric duals to a fixed graph

Regarding Question 1: you can very explicitly express the chromatic number of a dual graph, namely as the flow number of the primal graph (see for example: Wikipedia: Nowhere-zero flow).
Maybe a brief ...

1
vote

### Chordless cycles and planarity in graphs

I believe there is a characterization like the one you mention.
The de Fraysseix–Rosenstiehl planarity criterion traverses a given graph with a depth-first search and characterizes the way edges can ...

1
vote

### Cayley graph of $A_5$ with generators $(1,2,3,4,5),(1,4,3,2,5)$

There are computer programs to try, although I don't know how fast they are (the problem at hand is NP-complete).
E.g. Sagemath has an implementation of genus computation:
http://doc.sagemath.org/...

1
vote

Accepted

### Maximum genus of an abstract "cycle complex"

Let's first consider the special case that each node appears in exactly two sets in $C$. (Nodes that only appear in one set are irrelevant and can be deleted without changing the possible embeddings, ...

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

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

#### Related Tags

topological-graph-theory × 77graph-theory × 67

co.combinatorics × 36

discrete-geometry × 14

reference-request × 9

graph-drawing × 7

at.algebraic-topology × 5

embeddings × 5

planar-graphs × 5

algorithms × 4

graph-colorings × 4

graph-minors × 3

knot-link × 3

gn.general-topology × 2

knot-theory × 2

homology × 2

extremal-graph-theory × 2

genus × 2

gr.group-theory × 1

rt.representation-theory × 1

gt.geometric-topology × 1

mg.metric-geometry × 1

cv.complex-variables × 1

soft-question × 1

finite-groups × 1