Bar 1-visibility conjecture for 1-planar graphs

From papers

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.

Progress summary

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

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.