Intersection Dimension of Bipartite Graphs

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F14%3A10190766" target="_blank" >RIV/00216208:11320/14:10190766 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-06089-7_23" target="_blank" >http://dx.doi.org/10.1007/978-3-319-06089-7_23</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-06089-7_23" target="_blank" >10.1007/978-3-319-06089-7_23</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Intersection Dimension of Bipartite Graphs

Popis výsledku v původním jazyce

We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes definedas intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete.

Název v anglickém jazyce

Intersection Dimension of Bipartite Graphs

Popis výsledku anglicky

We introduce a concept of intersection dimension of a graph with respect to a graph class. This generalizes Ferrers dimension, boxicity, and poset dimension, and leads to interesting new problems. We focus in particular on bipartite graph classes definedas intersection graphs of two kinds of geometric objects. We relate well-known graph classes such as interval bigraphs, two-directional orthogonal ray graphs, chain graphs, and (unit) grid intersection graphs with respect to these dimensions. As an application of these graph-theoretic results, we show that the recognition problems for certain graph classes are NP-complete.

Druh

D - Stať ve sborníku

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2014

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 statě ve sborníku

Theory and Applications of Models of Computation

ISBN

978-3-319-06088-0

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

18

Strana od-do

323-340

Název nakladatele

Springer

Místo vydání

Switzerland

Místo konání akce

Chennai, Indie

Datum konání akce

11. 4. 2014

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—