Skip to main content
2 of 3
added 94 characters in body
Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187

As requested by Jukka Kohonen, I'll turn my comment into an answer.

The answer is in general no. If such an embedding exists, then the red subgraph and blue subgraph are both planar. However, every $n$-vertex planar graph has at most $3n-6$ edges. So, any $n$-vertex graph with at least $6n-11$ edges is a counterexample.

The minimum number of colours required for such an embedding is often called geometric thickness. For example, geometric thickness is mentioned on the Wikipedia page for [graph thickness][1], which is the minimum number of planar subgraphs that partition the edge set of a graph (where the embedding is not necessarily the same for each planar subgraph).

https://en.wikipedia.org/wiki/Thickness_(graph_theory)#:~:text=A%20different%20graph%20invariant%2C%20the,drawn%20simultaneously%20with%20straight%20edges.

Tony Huynh
  • 32.1k
  • 11
  • 112
  • 187