Return to Question

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

Or see this link .

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

Or see   this link for the hexagonal graph.

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

Or see this link .

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

A $1$-planar graph is a graph which has a drawing on the plane such that each edge has at most one crossing.

I used nauty to generate all 3-regular graphs up to order 12, and checked each one of them individually. They all turned out to be 1-planar graphs.

My question is whether it is possible to construct a 3-regular non-1-planar graph.

I believe that it definitely exists.

I also conducted experiments on graphs with relatively large crossing numbers, but unfortunately, they were all 1-planar graphs. For example: The smallest 6-crossing cubic graph is the Desargues graph, with 20 vertices.

This problem is related to the question Why is the crossing number of Tutte 12-cage 170?, because we know that the crossing number of an $n$-order 1-planar graph is less than or equal to $n-2$ (see [1]).

• [1] Czap J, Hudák D. On drawings and decompositions of 1-planar graphs[J]. the electronic journal of combinatorics, 2013: P54-P54.

If the crossing number of Tutte 12-cage (126 vertices)is greater than or equal to $125$, then it is the 3-regular non- 1-planar graph we are looking for. Unfortunately, it seems that the crossing number of Tutte 12-cage is unknown. It would still be helpful if we knew a good lower bound of Tutte 12-cage.

Edit 1： As reminded by Joseph O'Rourke, Coxeter graph is a candidate. The following embedding is from Wikipedia and it almost has a 1-planar embedding, except for one edge that will cross twice.

Edit 2: Thanks to Sam Hopkins for the reminder, the above sentence in Edit 1 should be corrected to: 3 of the edges will cross twice (not just one edge).