Seminar • Algorithms and Complexity • The Basis Number of 1-planar Graphs

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.

To attend this seminar in person, please go to DC 1302. You can also attend virtually on Zoom at https://uwaterloo.zoom.us/j/95291335725.