TY - GEN
T1 - Monotone drawings of graphs with fixed embedding
AU - Angelini, Patrizio
AU - Didimo, Walter
AU - Kobourov, Stephen
AU - McHedlidze, Tamara
AU - Roselli, Vincenzo
AU - Symvonis, Antonios
AU - Wismath, Stephen
N1 - Funding Information:
Research partially supported by the MIUR project AlgoDEEP prot. 2008TFBWL4, by the ESF project 10-EuroGIGA-OP-003 GraDR “Graph Drawings and Representations”, by NSERC, and by the European Union (European Social Fund - ESF) and Greek national funds through the Operational Program “Education and Lifelong Learning’” of the National Strategic Reference Framework (NSRF) - Research Funding Program: Heracleitus II. Investing in knowledge society through the European Social Fund. Work on these results began at the 6th Bertinoro Workshop on Graph drawing. Discussion with other participants is gratefully acknowledged.
PY - 2012
Y1 - 2012
N2 - 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 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 embedding-preserving monotone drawings with straight-line edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time.
AB - 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 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 embedding-preserving monotone drawings with straight-line edges, and we show that biconnected embedded planar graphs and outerplane graphs always admit such drawings, which can be computed in linear time.
UR - http://www.scopus.com/inward/record.url?scp=84455209585&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84455209585&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-25878-7_36
DO - 10.1007/978-3-642-25878-7_36
M3 - Conference contribution
AN - SCOPUS:84455209585
SN - 9783642258770
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 379
EP - 390
BT - Graph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers
T2 - 19th International Symposium on Graph Drawing, GD 2011
Y2 - 21 September 2011 through 23 September 2011
ER -