Monotone drawings of graphs with fixed embedding

Patrizio Angelini, Walter Didimo, Stephen Kobourov, Tamara McHedlidze, Vincenzo Roselli, Antonios Symvonis, Stephen Wismath

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationGraph Drawing - 19th International Symposium, GD 2011, Revised Selected Papers
Number of pages12
StatePublished - 2012
Event19th International Symposium on Graph Drawing, GD 2011 - Eindhoven, Netherlands
Duration: Sep 21 2011Sep 23 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume7034 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other19th International Symposium on Graph Drawing, GD 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Monotone drawings of graphs with fixed embedding'. Together they form a unique fingerprint.

Cite this