Bar 1-visibility conjecture for 1-planar graphs

About 13 years old · traced to

Let GG be a graph. It is 1-planar if it has a drawing in the plane in which each edge is crossed by at most one other edge. It is bar 1-visible if it has a bar 1-visibility drawing: vertices are represented by pairwise disjoint horizontal bars, and each edge is represented by a vertical segment joining the bars of its endpoints and crossing at most one bar belonging to another vertex.

Bar 1-visibility conjecture. Every 1-planar graph is a bar 1-visible graph.

The conjecture arises because the authors constructed bar 1-visibility drawings for every 1-planar graph they considered, but did not have a formal proof. The paper gives linear-time constructions for several classes of 1-planar graphs, while the general implication remains open.

References

Primary source

Shaheena Sultana, Md. Saidur Rahman, Arpita Roy and Suraiya Tairin, “Bar 1-Visibility Drawings of 1-Planar Graphs”, arXiv:1302.4870 (2013).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.