About: Faithful Representations of Graphs by Islands in the Extended Grid

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Faithful Representations of Graphs by Islands in the Extended Grid Goto Sponge NotDistinct Permalink

An Entity of Type : http://linked.opendata.cz/ontology/domain/vavai/Vysledek, within Data Space : linked.opendata.cz associated with source document(s)

Attributes	Values
rdf:type	skos:Concept http://linked.opendata.cz/ontology/domain/vavai/Vysledek
Description	We investigate embeddings of graphs into the infinite extended grid graph, where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k. We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k { 3 and k } 5; the cases k = 3, 4, 5 remain open. We investigate embeddings of graphs into the infinite extended grid graph, where the vertices are represented by subtrees of the grid (called islands), and the edges are represented by the usual grid edges joining the islands. Somewhat unexpectedly, these graphs turn out to unify such seemingly unrelated graph classes as the string graphs and the induced subgraphs of the extended grid. The connection is established by limiting the size (number of vertices) k of the representing islands. We study the problem of representability of an input graph G by islands of size at most k. We conjecture that this problem is NP-complete for any positive integer k, and prove the conjecture for k { 3 and k } 5; the cases k = 3, 4, 5 remain open. (en)
Title	Faithful Representations of Graphs by Islands in the Extended Grid Faithful Representations of Graphs by Islands in the Extended Grid (en)
skos:prefLabel	Faithful Representations of Graphs by Islands in the Extended Grid Faithful Representations of Graphs by Islands in the Extended Grid (en)
skos:notation	RIV/00216208:11320/10:10057003!RIV11-MSM-11320___
http://linked.open...avai/riv/aktivita	P Z
http://linked.open...avai/riv/aktivity	P(1M0545), Z(MSM0021620839)
http://linked.open...vai/riv/dodaniDat	2011
http://linked.open...aciTvurceVysledku	Kratochvíl, Jan Vyskočil, Tomáš
http://linked.open.../riv/druhVysledku	D - Článek ve sborníku
http://linked.open...iv/duvernostUdaju	S - Úplné a pravdivé údaje nepodléhající ochraně podle zvláštních právních předpisů
http://linked.open...titaPredkladatele	Univerzita Karlova v Praze / Matematicko-fyzikální fakulta
http://linked.open...dnocenehoVysledku	258704
http://linked.open...ai/riv/idVysledku	RIV/00216208:11320/10:10057003
http://linked.open...riv/jazykVysledku	eng - angličtina
http://linked.open.../riv/klicovaSlova	Extended Grid; Graphs; Geometric Representations (en)
http://linked.open.../riv/klicoveSlovo	Extended Grid Geometric Representations Graphs
http://linked.open...ontrolniKodProRIV	[0F63E9BB1260]
http://linked.open...v/mistoKonaniAkce	Oaxaca
http://linked.open...i/riv/mistoVydani	Berlin-Heidelberg
http://linked.open...i/riv/nazevZdroje	LATIN 2010: Theoretical Informatics
http://linked.open...in/vavai/riv/obor	BD
http://linked.open...ichTvurcuVysledku	2 (xsd:int)
http://linked.open...cetTvurcuVysledku	4 (xsd:int)
http://linked.open...vavai/riv/projekt	Institute for Theoretical Computer Science
http://linked.open...UplatneniVysledku	2010
http://linked.open...iv/tvurceVysledku	Kratochvíl, Jan Vyskočil, Tomáš Hell, Pavol Coury, Michael
http://linked.open...vavai/riv/typAkce	WRD - Světová
http://linked.open...ain/vavai/riv/wos	000279661700012
http://linked.open.../riv/zahajeniAkce	2010-04-19 (xsd:date)
http://linked.open...n/vavai/riv/zamer	Metody moderní matematiky a jejich aplikace
issn	0302-9743
number of pages	12 (xsd:int)
http://purl.org/ne...btex#hasPublisher	SPRINGER
https://schema.org/isbn	978-3-642-12199-9
http://localhost/t...ganizacniJednotka	11320
is http://linked.open...avai/riv/vysledek of	Faithful Representations of Graphs by Islands in the Extended Grid Faithful Representations of Graphs by Islands in the Extended Grid Faithful Representations of Graphs by Islands in the Extended Grid

Faceted Search & Find service v1.16.118 as of Jun 21 2024

Alternative Linked Data Documents: ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3240 as of Jun 21 2024, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (126 GB total memory, 58 GB memory in use)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software