Column Planarity and Partially-Simultaneous Geometric Embedding

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985807%3A_____%2F17%3A00483679" target="_blank" >RIV/67985807:_____/17:00483679 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.7155/jgaa.00446" target="_blank" >http://dx.doi.org/10.7155/jgaa.00446</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.7155/jgaa.00446" target="_blank" >10.7155/jgaa.00446</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Column Planarity and Partially-Simultaneous Geometric Embedding

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Column Planarity and Partially-Simultaneous Geometric Embedding

Popis výsledku anglicky

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.

Druh

J_SC - Článek v periodiku v databázi SCOPUS

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Journal of Graph Algorithms and Applications

ISSN

1526-1719

e-ISSN

—

Svazek periodika

21

Číslo periodika v rámci svazku

6

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

20

Strana od-do

983-1002

Kód UT WoS článku

—

EID výsledku v databázi Scopus

2-s2.0-85037335542