Column Planarity and Partial Simultaneous Geometric EmbeddingEvans, 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 2426, 2014 , pp. 259271(Official URL: http://dx.doi.org/10.1007/9783662458037_22). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_22
AbstractWe 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 xcoordinates to the vertices in R such that any assignment of ycoordinates to them produces a partial embedding that can be completed to a plane straightline 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 nvertex 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 kPSGEs 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/17PSGE, two outerpaths admit an n/4PSGE, and an outerpath and a tree admit a 11n/34PSGE.
Actions (login required)
