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 ...
- 32.1k
11
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 ...
- 68.8k
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 ...
- 935
7
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 ...
- 68.8k
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,051
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,101
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 ...
- 687
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 ...
- 32.1k
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 $...
- 12.4k
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 ...
- 1,617
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=(...
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 ...
- 1,617
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 ...
- 6,101
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 ...
- 296
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$, $...
- 94
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 ...
- 32.1k
3
votes
Do triple-linked graphs exist?
I have since come across the following paper which seems to answer the question affirmatively in a very strong sense:
E. Flapan, B. Mellor, R. Naimi, "Intrinsic linking and knotting are ...
- 13.6k
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,071
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 ...
- 6,101
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 ...
- 96.4k
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}$.)
...
- 8,597
2
votes
Accepted
Do triple-linked graphs exist?
Yes.
Theorem 1.
For every $k$ there exists $N=N(k)$ such that in every embedding of the complete tripartite graph $K_{N,N,N}$ into $\mathbb{R}^3$ there are $k$ disjoint pairwise linked triangles; in ...
- 6,101
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 ...
- 277
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,319
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 ...
- 105
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 ...
- 265
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/...
- 14k
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, ...
- 13.6k
Only top scored, non community-wiki answers of a minimum length are eligible