Seminar • Algorithms and Complexity • On Edge Density of arc-RAC Graphs

Monday, July 18, 2022 10:00 am - 11:00 am EDT (GMT -04:00)

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.