Four-bend necessity conjecture for planar graph EPG representations
An EPG representation of a graph represents each vertex by a path in the square grid, with adjacency corresponding to sharing a grid edge; a path has a bend at each change of grid direction. Four-bend necessity conjecture. There exists a planar graph such that every EPG representation of contains at least one path with four bends. The source places this statement in the conclusions alongside the open determination of the maximum bend-number of planar graphs, while its preceding theorem establishes only that this maximum is either three or four.
References
Primary source
Daniel Heldt, Kolja Knauer and Torsten Ueckerdt, “On the bend-number of planar and outerplanar graphs”, arXiv:1112.3353 (2011).
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.