Monotone Drawings of Graphs with Fixed Embedding
- 3 May 2013
- journal article
- research article
- Published by Springer Science and Business Media LLC in Algorithmica
- Vol. 71 (2), 233-257
- https://doi.org/10.1007/s00453-013-9790-3
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. 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.Keywords
This publication has 11 references indexed in Scilit:
- Monotone Drawings of GraphsJournal of Graph Algorithms and Applications, 2012
- An Algorithm to Construct Greedy Drawings of TriangulationsJournal of Graph Algorithms and Applications, 2010
- Some Results on Greedy Embeddings in Metric SpacesDiscrete & Computational Geometry, 2009
- On a conjecture related to geometric routingTheoretical Computer Science, 2005
- A Linear Time Implementation of SPQR-TreesLecture Notes in Computer Science, 2001
- On-Line Planarity TestingSIAM Journal on Computing, 1996
- On-line maintenance of triconnected components with SPQR-treesAlgorithmica, 1996
- Upward planarity testingOrder, 1995
- Triangulating a simple polygon in linear timeDiscrete & Computational Geometry, 1991
- Drawing plane graphs nicelyActa Informatica, 1985