Column planarity and partial simultaneous geometric embedding

W.S. Evans, V.J.J. Kusters, M. Saumell, B. Speckmann

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)
60 Downloads (Pure)

Samenvatting

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 e¿>¿0 and any sufficiently large n, there exists an n-vertex tree in which every column planar subset has size at most (5/6¿+¿e)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.
Originele taal-2Engels
TitelGraph Drawing (22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014, Revised Selected Papers)
RedacteurenC. Duncan, A. Symvonis
Plaats van productieBerlin
UitgeverijSpringer
Pagina's259-271
ISBN van geprinte versie978-3-662-45802-0
DOI's
StatusGepubliceerd - 2014
Evenement22nd International Symposium on Graph Drawing (GD 2014) - Würzburg, Duitsland
Duur: 24 sep 201426 sep 2014
Congresnummer: 22
http://gd2014.informatik.uni-wuerzburg.de/

Publicatie series

NaamLecture Notes in Computer Science
Volume8871
ISSN van geprinte versie0302-9743

Congres

Congres22nd International Symposium on Graph Drawing (GD 2014)
Verkorte titelGD 2014
LandDuitsland
StadWürzburg
Periode24/09/1426/09/14
Ander22nd International Symposium on Graph Drawing
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Column planarity and partial simultaneous geometric embedding'. Samen vormen ze een unieke vingerafdruk.

Citeer dit