CS 269S, Fall 2011: Theory Seminar
DBH 1433
18 November 2011:

Speaker: Lowell Trott

Title: On Embedding a Graph in the Grid with the Maximum Number of Bends and Other Bad Features

Abstract: Graph Drawing is (usually) concerned with the production of readable representations of graphs. In this paper, instead of investigating how to produce "good" drawings, we tackle the opposite problem of producing "bad" drawings. In particular, we study how to construct orthogonal drawings with many bends along the edges and with large area. Our results show surprising contact points, in Graph Drawing, between the computational cost of niceness and the one of ugliness.