License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2013.21
URN: urn:nbn:de:0030-drops-44029
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4402/
Go to the corresponding LIPIcs Volume Portal

Grohe, Martin ; Kreutzer, Stephan ; Siebertz, Sebastian

Characterisations of Nowhere Dense Graphs (Invited Talk)

pdf-format:
44.pdf (0.5 MB)

Abstract

Nowhere dense classes of graphs were introduced by Nesetril and Ossona de Mendez as a model for "sparsity" in graphs. It turns out that nowhere dense classes of graphs can be characterised in many different ways and have been shown to be equivalent to other concepts studied in areas such as (finite) model theory. Therefore, the concept of nowhere density seems to capture a natural property of graph classes generalising for example classes of graphs which exclude a fixed minor, have bounded degree or bounded local tree-width. In this paper we give a self-contained introduction to the concept of nowhere dense classes of graphs focussing on the various ways in which they can be characterised. We also briefly sketch algorithmic applications these characterisations have found in the literature.

BibTeX - Entry

@InProceedings{grohe_et_al:LIPIcs:2013:4402,
  author =	{Martin Grohe and Stephan Kreutzer and Sebastian Siebertz},
  title =	{{Characterisations of Nowhere Dense Graphs (Invited Talk)}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{21--40},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Anil Seth and Nisheeth K. Vishnoi},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4402},
  URN =		{urn:nbn:de:0030-drops-44029},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.21},
  annote =	{Keywords: Graph Algorithms, Algorithmic Graph Structure Theory, Finite  Model Theory, Nowhere Dense Classes of Graphs}
}

Keywords: Graph Algorithms, Algorithmic Graph Structure Theory, Finite Model Theory, Nowhere Dense Classes of Graphs
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)
Issue Date: 2013
Date of publication: 10.12.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI