Extending Convex Drawings of Graphs

11.11.2010, 17:30 Uhr


Informatik-Hauptgebäude (50.34),
SR 301 (3. OG),
Am Fasanengarten 5, 76131 Karlsruhe


Prof. Seok-Hee Hong, University of Sydney


Plakat [PDF]

Informatik-Sonderkolloquium zum Thema »Extending Convex Drawings of Graphs«

Extending Convex Drawings of Graphs

Graph Drawing has attracted much attention over the last twenty years due to its wide range of applications, such as VLSI design, social networks, software engineering and bioinformatics.
A straight-line drawing is called a »convex drawing« if every facial cycle is drawn as a convex polygon. Convex representation of graphs is a well- established aesthetic in Graph Drawing, however not all planar graphs admit a convex drawing as observed by Steinitz, Tutte and Thomassen earlier.

In this talk, we introduce two new notions of drawings, »inner-convex drawings« and »star-shaped drawings«, as natural extensions of convex drawings. We present various results including characterisation, testing, embedding and drawing algorithms. Our results extend the classical results by Tutte, and include results by Thomassen and Steinitz as a special case.

Bio: Seok-Hee Hong is an associate professor and principal research fellow at the University of Sydney. Her research interests include Graph Drawing, Information Visualisation and Visual Analytics.