The beta version of DROPS 2 is now publicly available! Check this page out at DROPS 2 now!


License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.6.11.35
URN: urn:nbn:de:0030-drops-70385
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7038/
Go back to Dagstuhl Reports

Hong, Sok-Hee ; Kaufmann, Michael ; Kobourov, Stephen G. ; Pach, János
Weitere Beteiligte (Hrsg. etc.): Seok-Hee Hong and Michael Kaufmann and Stephen G. Kobourov and János Pach

Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)

pdf-format:
dagrep_v006_i011_p035_s16452.pdf (1 MB)

Abstract

This report summarizes Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics'' and documents the talks and discussions.
The seminar brought together 29 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. The common interest was in the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with three introductory talks by experts in the different fields. Abstracts of these talks are collected in this report. Next we discussed and grouped together open research problems about beyond planar graphs, such as their combinatorial structures (e.g, thickness, crossing number, coloring), their topology (e.g., string graph representation), their geometric representations (e.g., straight-line drawing, visibility representation, contact representation), and applications (e.g., algorithms for real-world network visualization). Four working groups were formed and a report from each group is included here.

BibTeX - Entry

@Article{hong_et_al:DR:2017:7038,
  author =	{Sok-Hee Hong and Michael Kaufmann and Stephen G. Kobourov and J{\'a}nos Pach},
  title =	{{Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452)}},
  pages =	{35--62},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{6},
  number =	{11},
  editor =	{Seok-Hee Hong and Michael Kaufmann and Stephen G. Kobourov and J{\'a}nos Pach},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7038},
  URN =		{urn:nbn:de:0030-drops-70385},
  doi =		{10.4230/DagRep.6.11.35},
  annote =	{Keywords: graph drawing, graph algorithms, graph theory, geometric algorithms, combinatorial geometry, visualization}
}

Keywords: graph drawing, graph algorithms, graph theory, geometric algorithms, combinatorial geometry, visualization
Collection: Dagstuhl Reports, Volume 6, Issue 11
Issue Date: 2017
Date of publication: 23.03.2017

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