2013/11/01 by Grigoriev, Alexander, Koutsonas, Athanassios, Thilikos, Dimitrios M.
#05C10 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2
paper · doi:10.48550/arxiv.1311.0137
A graph G is ξ-nearly planar if it can be embedded in the sphere so that each of its edges is crossed at most ξ times. The family of ξ-nearly planar graphs is widely extending the notion of planarity. We introduce an alternative parameterized graph family extending the notion of planarity, the λ-flat graphs, this time defined as powers of plane graphs in regard to a novel notion of distance, the wall-by-wall distance. We show that the two parameterized graph classes are parametrically equivalent.