Seminar • Algorithms and Complexity • On Edge Density of arc-RAC GraphsExport this event to calendar

Monday, July 18, 2022 — 10:00 AM to 11:00 AM EDT

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.


To join this seminar on Zoom, please go to https://arizona.zoom.us/j/84319917495.

Location 
DC 1304 | Online seminar
200 University Avenue West

Waterloo, ON N2L 3G1
Canada
Event tags 

S M T W T F S
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6
  1. 2024 (80)
    1. April (8)
    2. March (22)
    3. February (25)
    4. January (25)
  2. 2023 (296)
    1. December (20)
    2. November (28)
    3. October (15)
    4. September (25)
    5. August (30)
    6. July (30)
    7. June (22)
    8. May (23)
    9. April (32)
    10. March (31)
    11. February (18)
    12. January (22)
  3. 2022 (245)
  4. 2021 (210)
  5. 2020 (217)
  6. 2019 (255)
  7. 2018 (217)
  8. 2017 (36)
  9. 2016 (21)
  10. 2015 (36)
  11. 2014 (33)
  12. 2013 (23)
  13. 2012 (4)
  14. 2011 (1)
  15. 2010 (1)
  16. 2009 (1)
  17. 2008 (1)