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

Authors Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, János Pach and all authors of the abstracts in this report



PDF
Thumbnail PDF

File

DagRep.6.11.35.pdf
  • Filesize: 1.12 MB
  • 28 pages

Document Identifiers

Author Details

Sok-Hee Hong
Michael Kaufmann
Stephen G. Kobourov
János Pach
and all authors of the abstracts in this report

Cite As Get BibTex

Sok-Hee Hong, Michael Kaufmann, Stephen G. Kobourov, and János Pach. Beyond-Planar Graphs: Algorithmics and Combinatorics (Dagstuhl Seminar 16452). In Dagstuhl Reports, Volume 6, Issue 11, pp. 35-62, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/DagRep.6.11.35

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.

Subject Classification

Keywords
  • graph drawing
  • graph algorithms
  • graph theory
  • geometric algorithms
  • combinatorial geometry
  • visualization

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail