Please note: This seminar will take place in DC 1304 and online.
Myroslav Kryven
University of Arizona
In a drawing of a graph crossings often clutter the drawing and make it hard to read. Therefore, crossing optimization is one of the fundamental problems in computer science. Since for many graphs (non-planar) we cannot get rid of crossings completely, the goal is to make them as distinguishable as possible. If the edges are drawn straight-line, we can maximize the crossing angle. Graphs that can be drawn with straight-line edges and right-angle crossings are called RAC graphs. They are well explored in the literature: they can have at most 4n − 10 edges (where n is the number of vertices) and this is tight, also their relation to other families of beyond-planar graphs (graphs that can be drawn with few crossings) is well understood.
In this talk we consider a generalization of RAC graphs where we allow drawing edges with circular arcs but still insist on right-angle crossings. We will discuss their edge density and look at some open problems around this class of graphs.