1
$\begingroup$

A graph is $k$-planar if it can be drawn on the plane such that each edge is crossed at most $k$ times. A graph together with a $k$-planar drawing is a $k$-plane graph. Hence, by definition, $0$-planar graphs are planar.

An edge contraction is an operation that removes an edge from a graph while simultaneously merging the two vertices that it previously joined. The resulting graph is denoted by $G/e$.

The following proposition can be obtained directly using Wagner's theorem.

Proposition Let $G$ be a planar graph and $e$ be an edge of $G$. Then $G/e$ is still a planar graph.

A natural question arises:

Question 1 Let $G$ be a $k$-planar graph with a $k$-planar drawing $D$ and $e$ be a non-crosssing edge in $D$. Then is $G/e$ still $k$-planar?

I felt $G/e$ is still $k$-planar, but never knew how to prove it strictly.

I have known that contracting a crossing edge of $D$ in Question 1 may not preserve $k$-planarity.

For example. Let $G$ be a 1-plane graph on the left of the following figure. $xy$ is a crossing edge of $G$. We get the graph $G/xy$ by contracting $xy$ that is not 1-planar (see the right graph in the following figure).

PS: Note that this fact that $G/xy$ is not only not 1-plane but also not 1-planar. This fact has been proven by this paper:

  • V. P. Korzhik, Minimal non-1-planar graphs, Discrete Math. 308 (2008), no. 7, 1319–1327, DOI 10.1016/j.disc.2007.04.009. MR2382367

enter image description here

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Draw a contracted vertex at $y$, cut all edges with end point $x$ near $x$, and continue them along $e$ towards $y$. $\endgroup$
    – Fedor Petrov
    Commented Aug 11, 2022 at 14:30
  • $\begingroup$ Nice! Sometimes I'm confused by the operation “near” . Why can $y$ be close to $x$ so that the k-plane drawing doesn't change (in the sense of homeomorphism)? Why can we continue the cutting edges alone $e$ towards $y$? Why are these processes guaranteed not to create new crossings？What is behind these seemingly intuitive practices? No offense, just curious. $\endgroup$
    – Licheng Zhang
    Commented Aug 11, 2022 at 16:07
  • $\begingroup$ It's confusion above that makes me look for a rigorous proof or explanation. $\endgroup$
    – Licheng Zhang
    Commented Aug 11, 2022 at 16:26
  • 1
    $\begingroup$ It first of all depends on how do we understand k-planar graphs. If the edges are piecewise linear, the situation is more clear. If they are just Jordan curves, I would start with a lemma that they may be replaced with piecewise linear edges meeting transversally. $\endgroup$
    – Fedor Petrov
    Commented Aug 11, 2022 at 17:07
  • $\begingroup$ Thank you. The line segments are somewhat easier to understand than Jordan curves. $\endgroup$
    – Licheng Zhang
    Commented Aug 13, 2022 at 8:50

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .