Intersection Dimension of Bipartite Graphs

Result code in 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>
Result on the web
<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>

Result language
angličtina
Original language name
Intersection Dimension of Bipartite Graphs
Original language description
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.
Czech name
—
Czech description
—

Project
Result was created during the realization of more than one project. More information in the Projects tab.
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

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

Similar results(10)