30.04.2015

Informatik-Kolloquium

Im Sommersemester 2015 findet im Rahmen des Informatik-Kolloquiums der folgende Vortrag statt:

Donnerstag, 30. April 2015, 10:15 Uhr, Seminarraum III

Dr. Steve Chaplick, TU Berlin

Canonical Orders of Planar Graphs and Their Applications

We review the concept of canonical orders of planar graphs and some of their applications. These orders were introduced by de Fraysseix, Pach, and Pollack (1990), later generalized by Kent (1996) and by Badent, Brandes, and Cornelsen (2011). They are the backbone of many graph drawing algorithms and allow one to obtain several interesting representations of planar graphs. As part of this talk we will discuss a linear-time algorithm to produce a canonical order from a given tri-connected planar graph. As a first application we will describe how one can produce a quadratic-area straight-line grid-drawing from a canonical order. We then show how to produce certain contact representations (e.g., triangle-contact, T-contact, and 3D-box-contact) of planar graphs from a canonical order. As part of this discussion of contact representations we introduce the concept of Schnyder realizers and their connection with planar graphs.