License
When quoting this document, please refer to the following
DOI: 10.4230/DagRep.9.2.123
URN: urn:nbn:de:0030-drops-108634
URL: http://drops.dagstuhl.de/opus/volltexte/2019/10863/
Go back to Dagstuhl Reports


Hong, Seok-Hee ; Kaufmann, Michael ; Pach, János ; Tóth, Csaba D.
Weitere Beteiligte (Hrsg. etc.): Seok-Hee Hong and Michael Kaufmann and János Pach and Csaba D. Tóth

Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)

pdf-format:
dagrep_v009_i002_p123_19092.pdf (8 MB)


Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 19092 "Beyond-Planar Graphs: Combinatorics, Models and Algorithms" which brought together 36 researchers in the areas of graph theory, combinatorics, computational geometry, and graph drawing. This seminar continued the work initiated in Dagstuhl Seminar 16452 "Beyond-Planar Graphs: Algorithmics and Combinatorics" and focused on the exploration of structural properties and the development of algorithms for so-called beyond-planar graphs, i.e., non-planar graphs that admit a drawing with topological constraints such as specific types of crossings, or with some forbidden crossing patterns. The seminar began with four talks about the results of scientific collaborations originating from the previous Dagstuhl seminar. Next we discussed open research problems about beyond planar graphs, such as their combinatorial structures (e.g., book thickness, queue number), their topology (e.g., simultaneous embeddability, gap planarity, quasi-quasiplanarity), their geometric representations (e.g., representations on few segments or arcs), and applications (e.g., manipulation of graph drawings by untangling operations). Six working groups were formed that investigated several of the open research questions. In addition, talks on related subjects and recent conference contributions were presented in the morning opening sessions. Abstracts of all talks and a report from each working group are included in this report.

BibTeX - Entry

@Article{hong_et_al:DR:2019:10863,
  author =	{Seok-Hee Hong and Michael Kaufmann and J{\'a}nos Pach and Csaba D. T{\'o}th},
  title =	{{Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)}},
  pages =	{123--156},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{2},
  editor =	{Seok-Hee Hong and Michael Kaufmann and J{\'a}nos Pach and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10863},
  URN =		{urn:nbn:de:0030-drops-108634},
  doi =		{10.4230/DagRep.9.2.123},
  annote =	{Keywords: combinatorial geometry, geometric algorithms, graph algorithms, graph drawing, graph theory, network visualization}
}

Keywords: combinatorial geometry, geometric algorithms, graph algorithms, graph drawing, graph theory, network visualization
Seminar: Dagstuhl Reports, Volume 9, Issue 2
Issue Date: 2019
Date of publication: 16.07.2019


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