Questions tagged [planar-graphs]

graphs that can be embedded into the plane, i.e. that can be drawn without crossings between the lines representing edges.

Filter by
Sorted by
Tagged with
36 votes
21 answers
6k views

Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...
Gil Kalai's user avatar
  • 24.2k
12 votes
0 answers
206 views

Does there exist 2-planar graph with chromatic number 8 or 9 or 10

A 2-planar graph is a graph that can be drawn in the plane so that each edge is crossed at most twice. It is known that every 2-planar graph satisfies that $|E(G)|\le 5(|V(G)|-2)$. This implies that ...
Xin Zhang's user avatar
  • 1,130
9 votes
2 answers
558 views

Do planar graphs have an acyclic two-coloring?

A graph has an acyclic two-coloring if its vertices can be colored with two colors such that each color class spans a forest. Does every planar graph have an acyclic two-coloring? An affirmative ...
domotorp's user avatar
  • 18.3k
7 votes
2 answers
240 views

There is a 3-connected 5-regular simple $n$-vertex planar graph iff $n$ satisfies....?

Is there any characterization on the set of integers $n$ such that there is a 3-connected 5-regular simple $n$-vertex planar graph?
Xin Zhang's user avatar
  • 1,130
3 votes
1 answer
124 views

Sharp upper bound of the number of edges for graphs of thickness two

A graph $G=(V,E)$ has thickness $2$ if $E$ can be written as a disjoint union $E=E_1\cup E_2$ so that $G_1:=(V,E_1),G_2:=(V,E_2)$ are planar graphs. For instance, $K_5$ has thickness $2$. It is known ...
Lorenzo Pompili's user avatar