Consider a graph $G$ with at least two unavoidable crossings, say, the disjoint union of two copies of $K_5$. Can such a graph always be drawn so that there is only one singular point (where all crossings happen)? I guess there is an easy proof that this is not possible.
$\begingroup$
$\endgroup$
2
asked Jan 17, 2017 at 18:56
-
1$\begingroup$ You might be interested in: Adams et al., "Knot projections with a single multi-crossing." Journal of Knot Theory and Its Ramifications, 24(03):1550011, 2015. $\endgroup$– Joseph O'RourkeCommented Jan 17, 2017 at 19:25
-
3$\begingroup$ No, as Tony Huynh had said. The minimum number of crossing-points for a graph $G$ is its degenerate crossing number $\mathrm{dcr}\; G$. Schaefer (The Graph Crossing Number and its Variants: A Survey, Electronic Journal of Combinatorics (2014), #DS21), p.41 cites Pach & Tóth's claim that for $G=K_{5,5}$, $\mathrm{dcr}\; G\leqslant15$ but $\mathrm{cr}\; G=16$. $\endgroup$– Rosie FCommented Jan 22, 2017 at 19:58
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
11
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 the standard assumption that every pair of edges which intersect in a drawing are not 'tangent' at the point of intersection. Suppose $D$ is a drawing of $G$ where all edges cross at the same point. Let $G'$ be the graph obtained from $D$ by introducing a new vertex at the crossing point and then suppressing all parallel edges. We claim that $|E(G')| \geq |E(G)|$. Let $H$ be the subgraph of $G$ induced by the edges which pass through the crossing point. Since no two crossing edges are tangent, $H$ contains at most one cycle (which must be a triangle). Therefore, $H$ has average degree at most $2$. It follows that $|E(G')| \geq |E(G)|$, as claimed. Thus, $G'$ is a planar graph with $n+1$ vertices and at least $3n-2$ edges. But this contradicts the fact that every $n$-vertex planar graph has at most $3n-6$ edges.
In particular, the above lemma implies that $K_7$ cannot be drawn so that all edges cross at the same point.
Acknowledgement. Many thanks to bof for help in making this answer converge to its present form (see the comments below).
answered Jan 17, 2017 at 19:11
-
1$\begingroup$ @GerryMyerson Yes, it works with $K_6$. You do not even need to know the crossing number of $K_6$ (only that it is at least $1$), since you get a planar graph with $7$ vertices and at least $16$ edges. I just wanted to use a sufficiently dense graph, so that the contradiction is obvious. $\endgroup$ Commented Jan 17, 2017 at 22:50
-
1$\begingroup$ I edited a $10$ into a $6$ accordingly though. Thanks. $\endgroup$ Commented Jan 17, 2017 at 23:32
-
1$\begingroup$ My previous try was faulty because some edges touched without crossing, but now I believe i have a correct drawing of $K_6$ with $15$ crossings all at one point. Let ABCDEF be a regular hexagon with center O. Draw the $6$ sides and $3$ diameters as straight line segments. Draw the edges AC, CE, EA as semicircles outside the hexagon. Draw the edges BD, DF, FB as circle arcs passing through O. $\endgroup$– bofCommented Aug 5, 2021 at 6:21
-
1$\begingroup$ @bof, well done! The 7-vertex graph you get by making the crossing point a vertex is a multigraph, with three edges from each of $B,D,F$ to $O$. So instead of $16$ edges, there are just $15$. $\endgroup$ Commented Aug 5, 2021 at 9:52
-
1$\begingroup$ @bof Thanks for the perseverence! I agree that your example works for $K_6$. I don't think it works for $K_7$ though. I will update my answer (again)! $\endgroup$ Commented Aug 5, 2021 at 11:05