Abstract
Given a plane graph G (i.e., a planar graph with a fixed planar embedding) and a simple cycle C in G whose vertices are mapped to a convex polygon, we consider the question whether this drawing can be extended to a planar straight-line drawing of G. We characterize when this is possible in terms of simple necessary conditions, which we prove to be sufficient. This also leads to a linear-time testing algorithm. If a drawing extension exists, it can be computed in the same running time.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Angelini, P., Di Battista, G., Frati, F., Jelínek, V., Kratochvíl, J., Patrignani, M., Rutter, I.: Testing planarity of partially embedded graphs. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 202–221. SIAM (2010)
Avis, D.: Generating rooted triangulations without repetitions. Algorithmica 16, 618–632 (1996)
Chambers, E.W., Eppstein, D., Goodrich, M.T., Löffler, M.: Drawing graphs in the plane with a prescribed outer face and polynomial area. Journal of Graph Algorithms and Applications 16(2), 243–259 (2012)
Duncan, C.A., Goodrich, M.T., Kobourov, S.G.: Planar drawings of higher-genus graphs. Journal of Graph Algorithms and Applications 15(1), 7–32 (2011)
Hong, S.-H., Nagamochi, H.: Convex drawings of graphs with non-convex boundary constraints. Discrete Applied Mathematics 156(12), 2368–2380 (2008)
Jelínek, V., Kratochvíl, J., Rutter, I.: A Kuratowski-type theorem for planarity of partially embedded graphs. Computational Geometry Theory & Applications 46(4), 466–492 (2013)
Mchedlidze, T., Nöllenburg, M., Rutter, I.: Drawing planar graphs with a prescribed inner face. CoRR, abs/1308.3370 (2013)
Pach, J., Wenger, R.: Embedding planar graphs at fixed vertex locations. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, pp. 263–274. Springer, Heidelberg (1999)
Patrignani, M.: On extending a partial straight-line drawing. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol. 3843, pp. 380–385. Springer, Heidelberg (2006)
Tutte, W.T.: How to draw a graph. Proc. London Math. Soc. 13(3), 743–768 (1963)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Mchedlidze, T., Nöllenburg, M., Rutter, I. (2013). Drawing Planar Graphs with a Prescribed Inner Face. In: Wismath, S., Wolff, A. (eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242. Springer, Cham. https://doi.org/10.1007/978-3-319-03841-4_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-03841-4_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-03840-7
Online ISBN: 978-3-319-03841-4
eBook Packages: Computer ScienceComputer Science (R0)