Please note: This seminar will take place in DC 1302 and online.
Bobby Miraftab, Postdoctoral Researcher
Algorithms, Graphs, and Geometry Lab, Carleton University
1-planar graphs refer to graphs that can be drawn in the plane with at most one crossing per edge. MacLane’s planarity criterion provides a characterization of planar graphs based on their cycle spaces. More precisely, it says a graph is planar if and only if it contains a 2-basis (a basis in which each edge belongs to at most two elements of the basis). The basis number of a graph G is defined as the smallest integer k for which G has a k-basis B, (B spans the cycle space of G and satisfies the condition that each edge of G is contained in at most k members of B).
We address the following question: does there exist a universal constant c such that every 1-planar graph has a c-basis? We give an affirmative answer for several classes of 1-planar graphs.