Search Results

Documents authored by Hong, Seok-Hee

Document
DOI: 10.4230/LIPIcs.GD.2024.13
The Price of Upwardness

Authors: Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyond planarity by considering upward k-planar drawings of DAGs in which the edges are monotonically increasing in a common direction and every edge is crossed at most k times for some integer k ≥ 1. We show that the number of crossings per edge in a monotone drawing is in general unbounded for the class of bipartite outerplanar, cubic, or bounded pathwidth DAGs. However, it is at most two for outerpaths and it is at most quadratic in the bandwidth in general. From the computational point of view, we prove that upward-k-planarity testing is NP-complete already for k = 1 and even for restricted instances for which upward planarity testing is polynomial. On the positive side, we can decide in linear time whether a single-source DAG admits an upward 1-planar drawing in which all vertices are incident to the outer face.
Cite as

Patrizio Angelini, Therese Biedl, Markus Chimani, Sabine Cornelsen, Giordano Da Lozzo, Seok-Hee Hong, Giuseppe Liotta, Maurizio Patrignani, Sergey Pupyrev, Ignaz Rutter, and Alexander Wolff. The Price of Upwardness. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.GD.2024.13,
  author =	{Angelini, Patrizio and Biedl, Therese and Chimani, Markus and Cornelsen, Sabine and Da Lozzo, Giordano and Hong, Seok-Hee and Liotta, Giuseppe and Patrignani, Maurizio and Pupyrev, Sergey and Rutter, Ignaz and Wolff, Alexander},
  title =	{{The Price of Upwardness}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.13},
  URN =		{urn:nbn:de:0030-drops-212977},
  doi =		{10.4230/LIPIcs.GD.2024.13},
  annote =	{Keywords: upward drawings, beyond planarity, upward k-planarity, upward outer-1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.16
GraphTrials: Visual Proofs of Graph Properties

Authors: Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Graph and network visualization supports exploration, analysis and communication of relational data arising in many domains: from biological and social networks, to transportation and powergrid systems. With the arrival of AI-based question-answering tools, issues of trustworthiness and explainability of generated answers motivate a greater role for visualization. In the context of graphs, we see the need for visualizations that can convince a critical audience that an assertion about the graph under analysis is valid. The requirements for such representations that convey precisely one specific graph property are quite different from standard network visualization criteria which optimize general aesthetics and readability. In this paper, we aim to provide a comprehensive introduction to visual proofs of graph properties and a foundation for further research in the area. We present a framework that defines what it means to visually prove a graph property. In the process, we introduce the notion of a visual certificate, that is, a specialized faithful graph visualization that leverages the viewer’s perception, in particular, pre-attentive processing (e. g. via pop-out effects), to verify a given assertion about the represented graph. We also discuss the relationships between visual complexity, cognitive load and complexity theory, and propose a classification based on visual proof complexity. Finally, we provide examples of visual certificates for problems in different visual proof complexity classes.
Cite as

Henry Förster, Felix Klesen, Tim Dwyer, Peter Eades, Seok-Hee Hong, Stephen G. Kobourov, Giuseppe Liotta, Kazuo Misue, Fabrizio Montecchiani, Alexander Pastukhov, and Falk Schreiber. GraphTrials: Visual Proofs of Graph Properties. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{forster_et_al:LIPIcs.GD.2024.16,
  author =	{F\"{o}rster, Henry and Klesen, Felix and Dwyer, Tim and Eades, Peter and Hong, Seok-Hee and Kobourov, Stephen G. and Liotta, Giuseppe and Misue, Kazuo and Montecchiani, Fabrizio and Pastukhov, Alexander and Schreiber, Falk},
  title =	{{GraphTrials: Visual Proofs of Graph Properties}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{16:1--16:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.16},
  URN =		{urn:nbn:de:0030-drops-213005},
  doi =		{10.4230/LIPIcs.GD.2024.16},
  annote =	{Keywords: Graph Visualization, Theory of Visualization, Visual Proof}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.17
Connectivity-Faithful Graph Drawing

Authors: Amyra Meidiana, Seok-Hee Hong, and Yongcheng Jing

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Connectivity is one of the important fundamental structural properties of graphs, and a graph drawing D should faithfully represent the connectivity structure of the underlying graph G. This paper investigates connectivity-faithful graph drawing leveraging the famous Nagamochi-Ibaraki (NI) algorithm, which computes a sparsification G_NI, preserving the k-connectivity of a k-connected graph G. Specifically, we first present CFNI, a divide-and-conquer algorithm, which computes a sparsification G_CFNI, which preserves the global k-connectivity of a graph G and the local h-connectivity of the h-connected components of G. We then present CFGD, a connectivity-faithful graph drawing algorithm based on CFNI, which faithfully displays the global and local connectivity structure of G. Extensive experiments demonstrate that CFNI outperforms NI with 66% improvement in the connectivity-related sampling quality metrics and 73% improvement in proxy quality metrics. Consequently, CFGD outperforms a naive application of NI for graph drawing, in particular with 62% improvement in stress metrics. Moreover, CFGD runs 51% faster than drawing the whole graph G, with a similar quality.
Cite as

Amyra Meidiana, Seok-Hee Hong, and Yongcheng Jing. Connectivity-Faithful Graph Drawing. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{meidiana_et_al:LIPIcs.GD.2024.17,
  author =	{Meidiana, Amyra and Hong, Seok-Hee and Jing, Yongcheng},
  title =	{{Connectivity-Faithful Graph Drawing}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{17:1--17:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.17},
  URN =		{urn:nbn:de:0030-drops-213015},
  doi =		{10.4230/LIPIcs.GD.2024.17},
  annote =	{Keywords: Graph connectivity, Faithful graph drawing, Graph sparsification}
}
Document
Poster Abstract
DOI: 10.4230/LIPIcs.GD.2024.49
Introducing Fairness in Graph Visualization (Poster Abstract)

Authors: Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract
Information visualization tools are an essential component of many data-driven decision-making systems that rely on human feedback. The aim of this paper is to propose a novel research direction focused on fair visualizations of graphs.
Cite as

Seok-Hee Hong, Giuseppe Liotta, Fabrizio Montecchiani, Martin Nöllenburg, and Tommaso Piselli. Introducing Fairness in Graph Visualization (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 49:1-49:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{hong_et_al:LIPIcs.GD.2024.49,
  author =	{Hong, Seok-Hee and Liotta, Giuseppe and Montecchiani, Fabrizio and N\"{o}llenburg, Martin and Piselli, Tommaso},
  title =	{{Introducing Fairness in Graph Visualization}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{49:1--49:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.49},
  URN =		{urn:nbn:de:0030-drops-213338},
  doi =		{10.4230/LIPIcs.GD.2024.49},
  annote =	{Keywords: Network visualization, Fairness, Stress minimization}
}
Document
DOI: 10.4230/DagRep.14.2.71
Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062)

Authors: Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster

Published in: Dagstuhl Reports, Volume 14, Issue 2 (2024)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 24062 "Beyond-Planar Graphs: Models, Structures and Geometric Representations". The seminar investigated beyond-planar graphs, in particular, their combinatorial and topological structures, computational complexity and algorithmics for recognition, geometric representations, and their applications to real-world network visualization. Compared to the previous two editions of the seminar, we focus more on aspects of combinatorics and geometry. The program consists of four invited talks on beyond planar graphs, open problem session, problem solving sessions and progress report sessions. Specific open problems include questions regarding the combinatorial structures and topology (e.g., k^+-real face graphs, beyond upward planar graphs, sparse universal geometric graphs, local-crossing-critical graphs), the geometric representations (e.g., constrained outer string graphs, rerouting curves on surface), and applications. The details of the invited talks and progress reports from each working groups are included in this report.
Cite as

Vida Dujmović, Seok-Hee Hong, Michael Kaufmann, János Pach, and Henry Förster. Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062). In Dagstuhl Reports, Volume 14, Issue 2, pp. 71-94, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@Article{dujmovic_et_al:DagRep.14.2.71,
  author =	{Dujmovi\'{c}, Vida and Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and F\"{o}rster, Henry},
  title =	{{Beyond-Planar Graphs: Models, Structures and Geometric Representations (Dagstuhl Seminar 24062)}},
  pages =	{71--94},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2024},
  volume =	{14},
  number =	{2},
  editor =	{Dujmovi\'{c}, Vida and Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and F\"{o}rster, Henry},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.14.2.71},
  URN =		{urn:nbn:de:0030-drops-204999},
  doi =		{10.4230/DagRep.14.2.71},
  annote =	{Keywords: Combinatorial geometry, Graph algorithm, Graph drawing, Graph theory, Network visualization}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ISAAC.2023.2
Faithful Graph Drawing (Invited Talk)

Authors: Seok-Hee Hong

Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)

Abstract
Graph drawing aims to compute good geometric representations of graphs in two or three dimensions. It has wide applications in network visualisation, such as social networks and biological networks, arising from many other disciplines. This talk will review fundamental theoretical results as well as recent advances in graph drawing, including symmetric graph drawing, generalisation of the Tutte’s barycenter theorem, Steinitz’s theorem, and Fáry’s theorem, and the so-called beyond planar graphs such as k-planar graphs. I will conclude my talk with recent progress in visualization of big complex graphs, including sublinear-time graph drawing algorithms and faithful graph drawing.
Cite as

Seok-Hee Hong. Faithful Graph Drawing (Invited Talk). In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hong:LIPIcs.ISAAC.2023.2,
  author =	{Hong, Seok-Hee},
  title =	{{Faithful Graph Drawing}},
  booktitle =	{34th International Symposium on Algorithms and Computation (ISAAC 2023)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-289-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{283},
  editor =	{Iwata, Satoru and Kakimura, Naonori},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.2},
  URN =		{urn:nbn:de:0030-drops-193044},
  doi =		{10.4230/LIPIcs.ISAAC.2023.2},
  annote =	{Keywords: Graph drawing, Planar graphs, Beyond planar graphs, Tutte’s barycenter theorem, Steinitz’s theorem, F\'{a}ry’s theorem, Sublinear-time graph drawing algorithm, Faithful graph drawing, Symmetric graph drawing}
}
Document
DOI: 10.4230/DagRep.9.2.123
Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092)

Authors: Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth

Published in: Dagstuhl Reports, Volume 9, Issue 2 (2019)

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.
Cite as

Seok-Hee Hong, Michael Kaufmann, János Pach, and Csaba D. Tóth. Beyond-Planar Graphs: Combinatorics, Models and Algorithms (Dagstuhl Seminar 19092). In Dagstuhl Reports, Volume 9, Issue 2, pp. 123-156, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{hong_et_al:DagRep.9.2.123,
  author =	{Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.},
  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 =	{Hong, Seok-Hee and Kaufmann, Michael and Pach, J\'{a}nos and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.2.123},
  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}
}
Document
Complete Volume
DOI: 10.4230/LIPIcs.ISAAC.2016
LIPIcs, Volume 64, ISAAC'16, Complete Volume

Authors: Seok-Hee Hong

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
LIPIcs, Volume 64, ISAAC'16, Complete Volume
Cite as

27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{hong:LIPIcs.ISAAC.2016,
  title =	{{LIPIcs, Volume 64, ISAAC'16, Complete Volume}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016},
  URN =		{urn:nbn:de:0030-drops-69067},
  doi =		{10.4230/LIPIcs.ISAAC.2016},
  annote =	{Keywords: Data Structures, Nonnumerical Algorithms and Problems, Optimization, Discrete Mathematics, Mathematical Software, Algorithms Problem Solving, Control Methods, and Search, Computational Geometry and Object Modeling}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ISAAC.2016.0
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers

Authors: Seok-Hee Hong

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract
Front Matter, Table of Contents, Preface, Program Committee, External Reviewers
Cite as

27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{hong:LIPIcs.ISAAC.2016.0,
  author =	{Hong, Seok-Hee},
  title =	{{Front Matter, Table of Contents, Preface, Program Committee, External Reviewers}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{0:i--0:xiv},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.0},
  URN =		{urn:nbn:de:0030-drops-67728},
  doi =		{10.4230/LIPIcs.ISAAC.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Program Committee, External Reviewers}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact