Column Planarity and Partial Simultaneous Geometric Embedding

Evans, William S. and Kusters, Vincent and Saumell, Maria and Speckmann, Bettina (2014) Column Planarity and Partial Simultaneous Geometric Embedding. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 259-271 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_22).

Full text not available from this repository.

Abstract

We introduce the notion of column planarity of a subset R of the vertices of a graph G. Informally, we say that R is column planar in G if we can assign x-coordinates to the vertices in R such that any assignment of y-coordinates to them produces a partial embedding that can be completed to a plane straight-line drawing of G. Column planarity is both a relaxation and a strengthening of unlabeled level planarity. We prove near tight bounds for column planar subsets of trees: any tree on n vertices contains a column planar set of size at least 14n/17 and for any ε > 0 and any sufficiently large n, there exists an n-vertex tree in which every column planar subset has size at most (5/6 + ε)n. We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partial SGE (PSGE). A PSGE of two graphs G 1 and G 2 allows some of their vertices to map to two different points in the plane. We show how to use column planar subsets to construct k-PSGEs in which k vertices are still mapped to the same point. In particular, we show that any two trees on n vertices admit an 11n/17-PSGE, two outerpaths admit an n/4-PSGE, and an outerpath and a tree admit a 11n/34-PSGE.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_22
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.700 Layering
M Methods > M.300 Dynamic / Incremental / Online
M Methods > M.900 Tree
P Styles > P.480 Layered
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.750 Topology
ID Code:1438

Repository Staff Only: item control page

References

Angelini, P., Geyer, M., Kaufmann, M., Neuwirth, D.: On a tree and a path with no geometric simultaneous embedding. In: Brandes, U., Cornelsen, S. (eds.) GD 2010. LNCS, vol. 6502, pp. 38–49. Springer, Heidelberg (2011)

Bläsius, T., Kobourov, S.G., Rutter, I.: Simultaneous embedding of planar graphs. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization (2013)

Bose, P., Dujmović, V., Hurtado, F., Langerman, S., Morin, P., Wood, D.R.: A polynomial bound for untangling geometric planar graphs. Disc. & Comp. Geom. 42(4), 570–585 (2009)

Brass, P., Cenek, E., Duncan, C.A., Efrat, A., Erten, C., Ismailescu, D.P., Kobourov, S.G., Lubiw, A., Mitchell, J.S.: On simultaneous planar graph embeddings. Comp. Geom. 36(2), 117–130 (2007)

Cabello, S., van Kreveld, M., Liotta, G., Meijer, H., Speckmann, B., Verbeek, K.: Geometric simultaneous embeddings of a graph and a matching. J. Graph Alg. Appl. 15(1), 79–96 (2011)

Cappos, J., Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Simultaneous graph embedding with bends and circular arcs. Comp. Geom. 42(2), 173–182 (2009)

Di Giacomo, E., Didimo, W., van Kreveld, M., Liotta, G., Speckmann, B.: Matched drawings of planar graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 183–194. Springer, Heidelberg (2008)

Di Giacomo, E., Didimo, W., Liotta, G., Meijer, H., Wismath, S.: Planar and quasi planar simultaneous geometric embedding. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 52–63. Springer, Heidelberg (2014)

Erten, C., Kobourov, S.G.: Simultaneous embedding of planar graphs with few bends. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 195–205. Springer, Heidelberg (2005)

Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Comp. Geom. 42(6), 704–721 (2009)

Estrella-Balderrama, A., Gassner, E., Jünger, M., Percan, M., Schaefer, M., Schulz, M.: Simultaneous geometric graph embeddings. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 280–290. Springer, Heidelberg (2008)

Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar graphs. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 37–49. Springer, Heidelberg (2008)

Frati, F., Kaufmann, M., Kobourov, S.G.: Constrained simultaneous and near-simultaneous embeddings. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 268–279. Springer, Heidelberg (2008)

Geyer, M., Kaufmann, M., Vrt’o, I.: Two trees which are self-intersecting when drawn simultaneously. Disc. Math. 309(7), 1909–1916 (2009)

Goaoc, X., Kratochvíl, J., Okamoto, Y., Shin, C.S., Spillner, A., Wolff, A.: Untangling a planar graph. Disc. & Comp. Geom. 42(4), 542–569 (2009)