Master’s Thesis Presentation • Algorithms and Complexity — Area Efficient Drawings of Outer-1-Planar GraphsExport this event to calendar

Monday, September 21, 2020 — 12:00 PM EDT

Please note: This master’s thesis presentation will be given online.

Pavle Bulatovic, Master’s candidate
David R. Cheriton School of Computer Science

Supervisor: Professor Therese Biedl

We study area-efficient drawings of planar graphs: embeddings of graphs on an integer grid so that the bounding box of the drawing is minimized. Our focus is on the class of outer-1-planar graphs; a family of planar graphs that can be drawn on the plane with all vertices on the outer-face so that each edge is crossed at most once. We first present two straight-line drawing algorithms that yield small area straight-line drawings for the subclass of complete outer-1-planar graphs. Further, we give an algorithm that produces an orthogonal drawing of any outer-1-plane graph in O(n log n) area while keeping the number of bends per edge relatively small.


To join this master’s thesis presentation on Zoom, please go to https://us02web.zoom.us/j/83186234331?pwd=N3dBc3Y1UUgwSkRoYkEyUnhRODlZQT09.

Location 
Online presentation
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
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
1
2
3
4
5
  1. 2020 (208)
    1. December (9)
    2. November (12)
    3. October (7)
    4. September (21)
    5. August (28)
    6. July (14)
    7. June (18)
    8. May (16)
    9. April (20)
    10. March (16)
    11. February (25)
    12. January (22)
  2. 2019 (255)
    1. December (21)
    2. November (25)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  3. 2018 (217)
  4. 2017 (36)
  5. 2016 (21)
  6. 2015 (36)
  7. 2014 (33)
  8. 2013 (23)
  9. 2012 (4)
  10. 2011 (1)
  11. 2010 (1)
  12. 2009 (1)
  13. 2008 (1)