This HTML5 document contains 57 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dctermshttp://purl.org/dc/terms/
yago-reshttp://yago-knowledge.org/resource/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
n10http://dbpedia.org/resource/File:
n18https://global.dbpedia.org/id/
dbthttp://dbpedia.org/resource/Template:
rdfshttp://www.w3.org/2000/01/rdf-schema#
n19https://drops.dagstuhl.de/opus/volltexte/2010/2500/
freebasehttp://rdf.freebase.com/ns/
n4http://commons.wikimedia.org/wiki/Special:FilePath/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
owlhttp://www.w3.org/2002/07/owl#
wikipedia-enhttp://en.wikipedia.org/wiki/
dbphttp://dbpedia.org/property/
dbchttp://dbpedia.org/resource/Category:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
wikidatahttp://www.wikidata.org/entity/
dbrhttp://dbpedia.org/resource/

Statements

Subject Item
dbr:Bidimensionality
rdfs:label
Bidimensionality
rdfs:comment
Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.
foaf:depiction
n4:Gamma_graph.jpg
dcterms:subject
dbc:Analysis_of_algorithms dbc:Approximation_algorithms dbc:Parameterized_complexity dbc:Graph_minor_theory
dbo:wikiPageID
28140890
dbo:wikiPageRevisionID
1102788150
dbo:wikiPageWikiLink
dbr:Neil_Robertson_(mathematician) dbr:Polynomial-time_approximation_scheme dbr:Kernelization dbr:Graph_embedding n10:Gamma_graph.jpg dbr:Connected_dominating_set dbr:J._ACM dbc:Approximation_algorithms dbr:Nerode_Prize dbr:Dominating_set dbr:Mohammad_Hajiaghayi dbr:Feedback_vertex_set dbr:Paul_Seymour_(mathematician) dbr:Longest_path dbr:Treewidth dbr:Erik_Demaine dbr:Vertex_cover dbr:Maximum_internal_spanning_tree dbc:Analysis_of_algorithms dbr:Edge_dominating_set dbr:Graph_minor dbr:Induced_matching dbr:Independent_set_(graph_theory) dbr:Halin's_grid_theorem dbr:Apex_graph dbr:Minor_(graph_theory) dbr:Fedor_Fomin dbc:Parameterized_complexity dbr:Parameterized_complexity dbr:Combinatorica dbr:SIAM_Journal_on_Discrete_Mathematics dbc:Graph_minor_theory dbr:Planar_graph
dbo:wikiPageExternalLink
n19:
owl:sameAs
wikidata:Q4904170 freebase:m.0cmcw6c yago-res:Bidimensionality n18:4YHz7
dbp:wikiPageUsesTemplate
dbt:Refbegin dbt:Main dbt:Refend dbt:Reflist dbt:Citation
dbo:thumbnail
n4:Gamma_graph.jpg?width=300
dbo:abstract
Bidimensionality theory characterizes a broad range of graph problems (bidimensional) that admit efficient approximate, fixed-parameter or kernel solutions in a broad range of graphs. These graph classes include planar graphs, map graphs, bounded-genus graphs and graphs excluding any fixed minor. In particular, bidimensionality theory builds on the graph minor theory of Robertson and Seymour by extending the mathematical results and building new algorithmic tools. The theory was introduced in the work of Demaine, Fomin, Hajiaghayi, and Thilikos, for which the authors received the Nerode Prize in 2015.
prov:wasDerivedFrom
wikipedia-en:Bidimensionality?oldid=1102788150&ns=0
dbo:wikiPageLength
11143
foaf:isPrimaryTopicOf
wikipedia-en:Bidimensionality