Drawing Planar Graphs with a Prescribed Inner Face

Mchedlidze, Tamara and Nöllenburg, Martin and Rutter, Ignaz (2013) Drawing Planar Graphs with a Prescribed Inner Face. In: 21st International Symposium, GD 2013, September 23-25, 2013, Bordeaux, France , pp. 316-327 (Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_28).

Full text not available from this repository.

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.

Item Type:Conference Paper
Classifications:P Styles > P.540 Planar
P Styles > P.720 Straight-line
ID Code:1385

Repository Staff Only: item control page

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)