DROPS

Document

Bringing Graph Databases and Network Visualization Together (Dagstuhl Seminar 22031)

Authors: Karsten Klein, Juan F. Sequeda, Hsiang-Yun Wu, and Da Yan

Published in: Dagstuhl Reports, Volume 12, Issue 1 (2022)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 22031 "Bringing Graph Databases and Network Visualization Together". Due to the ongoing restrictions caused by the COVID-19 pandemic, this purely on-site seminar had a reduced number of participants. Twenty-two researchers and practitioners from the Network Visualization and Graph Database communities met to initiate collaborative work and exchange between the two communities. The seminar served to establish a common understanding of the state of the art and the terminology in both communities, and to connect participants to tackle joint research challenges. Survey talks on the first days laid the foundations for subsequent plenary discussions and working groups. Further lightining talks during the next days gave more detailed insight into specific research questions and practical challenges. The contributions of the seminar include bringing the communities together, the identification of the top areas of research interest, and the characterization of research challenges and research questions. As an outcome, a position paper is planned, and further collaborations and joint publications are on the way.

Cite as

Karsten Klein, Juan F. Sequeda, Hsiang-Yun Wu, and Da Yan. Bringing Graph Databases and Network Visualization Together (Dagstuhl Seminar 22031). In Dagstuhl Reports, Volume 12, Issue 1, pp. 67-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@Article{klein_et_al:DagRep.12.1.67,
  author =	{Klein, Karsten and Sequeda, Juan F. and Wu, Hsiang-Yun and Yan, Da},
  title =	{{Bringing Graph Databases and Network Visualization Together (Dagstuhl Seminar 22031)}},
  pages =	{67--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2022},
  volume =	{12},
  number =	{1},
  editor =	{Klein, Karsten and Sequeda, Juan F. and Wu, Hsiang-Yun and Yan, Da},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.1.67},
  URN =		{urn:nbn:de:0030-drops-169218},
  doi =		{10.4230/DagRep.12.1.67},
  annote =	{Keywords: graph databases, network visualization, visual analytics}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.19

Untangling Circular Drawings: Algorithms and Complexity

Authors: Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

We consider the problem of untangling a given (non-planar) straight-line circular drawing δ_G of an outerplanar graph G = (V,E) into a planar straight-line circular drawing by shifting a minimum number of vertices to a new position on the circle. For an outerplanar graph G, it is clear that such a crossing-free circular drawing always exists and we define the circular shifting number shift°(δ_G) as the minimum number of vertices that need to be shifted to resolve all crossings of δ_G. We show that the problem Circular Untangling, asking whether shift°(δ_G) ≤ K for a given integer K, is NP-complete. Based on this result we study Circular Untangling for almost-planar circular drawings, in which a single edge is involved in all the crossings. In this case we provide a tight upper bound shift°(δ_G) ≤ ⌊n/2⌋-1, where n is the number of vertices in G, and present a polynomial-time algorithm to compute the circular shifting number of almost-planar drawings.

Cite as

Sujoy Bhore, Guangping Li, Martin Nöllenburg, Ignaz Rutter, and Hsiang-Yun Wu. Untangling Circular Drawings: Algorithms and Complexity. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 19:1-19:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.ISAAC.2021.19,
  author =	{Bhore, Sujoy and Li, Guangping and N\"{o}llenburg, Martin and Rutter, Ignaz and Wu, Hsiang-Yun},
  title =	{{Untangling Circular Drawings: Algorithms and Complexity}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{19:1--19:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.19},
  URN =		{urn:nbn:de:0030-drops-154528},
  doi =		{10.4230/LIPIcs.ISAAC.2021.19},
  annote =	{Keywords: graph drawing, straight-line drawing, outerplanarity, NP-hardness, untangling}
}

Search Results

Documents authored by Wu, Hsiang-Yun

Bringing Graph Databases and Network Visualization Together (Dagstuhl Seminar 22031)

Abstract

Cite as

Untangling Circular Drawings: Algorithms and Complexity

Abstract

Cite as

Thanks for your feedback!

Could not send message