Bar 1-visibility conjecture for 1-planar graphs
Let 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
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.