Monotone Drawings of Graphs with Fixed EmbeddingAngelini, Patrizio and Didimo, Walter and Kobourov, Stephen G. and Mchedlidze, Tamara and Roselli, Vincenzo and Symvonis, Antonios and Wismath, Stephen (2012) Monotone Drawings of Graphs with Fixed Embedding. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 379390(Official URL: http://dx.doi.org/10.1007/9783642258787_36). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642258787_36
AbstractA drawing of a graph is a monotone drawing if for every pair of vertices u and v, there is a path drawn from u to v that is monotone in some direction. In this paper we investigate planar monotone drawings in the fixed embedding setting, i.e., a planar embedding of the graph is given as part of the input that must be preserved by the drawing algorithm. In this setting we prove that every planar graph on n vertices admits a planar monotone drawing with at most two bends per edge and with at most 4n − 10 bends in total; such a drawing can be computed in linear time and requires polynomial area. We also show that two bends per edge are sometimes necessary on a linear number of edges of the graph. Furthermore, we investigate subclasses of planar graphs that can be realized as embeddingpreserving monotone drawings with straightline edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time.
Actions (login required)
