3
$\begingroup$

A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. 1 planar graph

I read the following paper, which stated the following fact about the rectilinear drawing of a 1-plane graph.

Thomassen, C. (1988), Rectilinear drawings of graphs. J. Graph Theory, 12: 335-341.https://doi.org/10.1002/jgt.3190120306

Theorem 3.1. Let $G$ be a graph represented as a normal drawing of index $0$ or $1$. Then there exists a rectilinear drawing equivalent to $G$ if and only if $G$ contains no $B-$ or $W-$configuration. enter image description here

From this theorem we know that a 1-planar graph satisfies any 1-plane drawing of it without $B-$ and $W-$configuration, then it has no rectilinear drawing.

But I haven't constructed a 1-planar graph without rectilinear drawing so far. It is even doubtful that it exists. This is one of my confusing points. Any advice would be helpful and thanks in advance!

Some concepts are added below:

  • Every finite graph can be drawn in the Euclidean plane such that any two edges have at most one point in common (in particular, two edges with a common end have no other point in common), and such that every point that is not a vertex and that is on two edges is on precisely two edges and is a cross-point for these two edges. We call such a drawing normal.

  • The maximum number of crosspoints on an edge is called the cross-index of the drawing.

$\endgroup$

1 Answer 1

2
$\begingroup$

The main result of the following paper states that a graph which has a 1-planar straight-line drawing has at most $4n-9$ edges, where $n$ is (as usual) the number of vertices:

Didimo, Walter, Density of straight-line 1-planar graph drawings, Inf. Process. Lett. 113, No. 7, 236-240 (2013). ZBL1259.05107.

On the other hand, it is not hard to come up with a 1-planar graph with $4n-8$ edges: take any drawing of a planar graph in which every face is a quadrilateral and add a pair of crossing edges to each face. For instance, applying this to the cube gives $K_8$ with a matching removed.

$\endgroup$
1
  • $\begingroup$ Great! thanks for your help! $\endgroup$
    – lcz
    Apr 20, 2021 at 15:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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