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. -

Angelini, P., Walter, D., Stephen, K., Tamara, M., Roselli, V., Antonios, S., et al. (2012). Monotone Drawings of Graphs with Fixed Embedding. In Proc. of 19th International Symposium on Graph Drawing (GD 2011) (pp.379-390). berlin : Springer Berlin Heidelberg [10.1007/978-3-642-25878-7_36].

Monotone Drawings of Graphs with Fixed Embedding

ANGELINI, PATRIZIO;ROSELLI, VINCENZO;
2012-01-01

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 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. -
2012
978-3-642-25877-0
Angelini, P., Walter, D., Stephen, K., Tamara, M., Roselli, V., Antonios, S., et al. (2012). Monotone Drawings of Graphs with Fixed Embedding. In Proc. of 19th International Symposium on Graph Drawing (GD 2011) (pp.379-390). berlin : Springer Berlin Heidelberg [10.1007/978-3-642-25878-7_36].
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11590/169776
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact