Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

A $1$-planar graph can be drawn in the plane so that each arc is crossed at most once by another arc. A $k$-planar graph can be drawn so that each arc is crossed at most $k$ times.

Planar graphs are $4$-colorable, and $1$-planar graphs are $6$-colorable. ($K_6$ is $1$-planar: image below from here.)

What bounds are known on the colorability of $k$-planar graphs?

This has likely been studied; I just don't know the results. Thanks for pointers!

Answered by Tony Huynh and David Eppstein: The chromatic number of a $k$-planar graph is $\Theta(\sqrt{k})$.

share|cite|improve this question

2 Answers 2

up vote 10 down vote accepted

Pach and Toth proved that if $G$ is a $k$-planar graph (with $k \geq 1$), then

$|E(G)| \leq 4.108 \sqrt{k} |V(G)|$.

Thus, every $k$-planar graph has a vertex of degree at most $\lfloor8.216 \sqrt{k}\rfloor$. By induction, it follows that $k$-planar graphs can be coloured with $\lfloor8.216 \sqrt{k}\rfloor+1$ colours.

For $1 \leq k \leq 4$, they prove a better bound of

$|E(G)| \leq (k+3)(|V(G)|-2)$.

Thus, we can do slightly better for small values of $k$. That is, 2-planar graphs are 10-colourable, 3-planar graphs are 12-colourable, and 4-planar graphs are 14-colourable.

For $k=3$, even better upper bound is known: $|E(G)| \leq 5.5(|V(G)|-2)$ (Pach, Radoicic, Tardos, Toth 2006)

share|cite|improve this answer
Thanks, Tony! In conjunction with David's remarks, this shows that the chromatic number is $\Theta(\sqrt{k})$. – Joseph O'Rourke May 28 '14 at 19:51

To complement Tony Huynh's answer, something proportional to $\sqrt k$ is also a lower bound on the chromatic number: there exist $k$-planar graphs that need this many colors. In particular, if one draws a complete graph of $\Theta(\sqrt k)$ vertices by placing the vertices on a circle and drawing the edges as line segments, the resulting drawing will be $k$-planar but the complete graph will require $\Omega(\sqrt k)$ colors.

share|cite|improve this answer
Nice lower-bound construction, David! Thanks! – Joseph O'Rourke May 28 '14 at 19:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.