Monotone Drawings of Graphs with Fixed Embedding
Angelini, Patrizio
Didimo, Walter Kobourov, Stephen Mchedlidze, Tamara Roselli, Vincenzo Symvonis, Antonios Wismath, Stephen
Didimo, Walter
Kobourov, Stephen
Mchedlidze, Tamara
Roselli, Vincenzo
Symvonis, Antonios
Wismath, Stephen
Citations
Altmetric:
Abstract
A 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 4 n 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 embedding-preserving monotone drawings with straight-line edges. In fact, we prove that biconnected embedded planar graphs and outerplane graphs always admit such drawings, and describe linear-time drawing algorithms for these two graph classes.
Description
Date
2015
Journal Title
Journal ISSN
Volume Title
Publisher
Research Projects
Organizational Units
Journal Issue
Keywords
Curve complexity, Fixed embedding, Monotone drawings, Planar graph drawing
Citation
Angelini, Patrizio, Walter Didimo, Stephen Kobourov, et al. “Monotone Drawings of Graphs with Fixed Embedding.” Algorithmica 71 (2): 233–57. 2015.