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.