Number of the records: 1
Column Planarity and Partially-Simultaneous Geometric Embedding
- 1.
SYSNO ASEP 0483679 Document Type J - Journal Article R&D Document Type Journal Article Subsidiary J Článek ve SCOPUS Title Column Planarity and Partially-Simultaneous Geometric Embedding Author(s) Barba, L. (CH)
Evans, W. (CA)
Hoffmann, M. (CH)
Kusters, V. (CH)
Saumell, Maria (UIVT-O) RID, SAI, ORCID
Speckmann, B. (NL)Source Title Journal of Graph Algorithms and Applications - ISSN 1526-1719
Roč. 21, č. 6 (2017), s. 983-1002Number of pages 20 s. Language eng - English Country US - United States Keywords column planarity ; unlabeled level planarity ; simultaneous geometric embedding Subject RIV BA - General Mathematics OECD category Pure mathematics Institutional support UIVT-O - RVO:67985807 EID SCOPUS 85037335542 DOI 10.7155/jgaa.00446 Annotation 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 the maximum size of column planar subsets of trees: every tree on n vertices contains a column planar set of size at least 14n/17 and for any epsilon > 0 and any sufficiently large n, there exists an n-vertex tree in which every column planar subset has size at most (5/6 + epsilon)n. In addition, we show that every outerplanar graph has a column planar set of size at least n/2. We also consider a relaxation of simultaneous geometric embedding (SGE), which we call partially-simultaneous geometric embedding (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, which are PSGEs in which at least k vertices are mapped to the same point for both graphs. In particular, we show that every two trees on n vertices admit an 11n/17-PSGE and every two outerplanar graphs admit an n/4-PSGE. Workplace Institute of Computer Science Contact Tereza Šírová, sirova@cs.cas.cz, Tel.: 266 053 800 Year of Publishing 2018
Number of the records: 1