7 Search Results for "Ravsky, Alexander"

Document
DOI: 10.4230/LIPIcs.GD.2025.24
String Graph Obstacles of High Girth and of Bounded Degree

Authors: Maria Chudnovsky, David Eppstein, and David Fischer

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A string graph is the intersection graph of curves in the plane. Kratochvíl previously showed the existence of infinitely many obstacles: graphs that are not string graphs but for which any edge contraction or vertex deletion produces a string graph. Kratochvíl’s obstacles contain arbitrarily large cliques, so they have girth three and unbounded degree. We extend this line of working by studying obstacles among graphs of restricted girth and/or degree. We construct an infinite family of obstacles of girth four; in addition, our construction is K_{2,3}-subgraph-free and near-planar (planar plus one edge). Furthermore, we prove that there is a subcubic obstacle of girth three, and that there are no subcubic obstacles of high girth. We characterize the subcubic string graphs as having a matching whose contraction yields a planar graph, and based on this characterization we find a linear-time algorithm for recognizing subcubic string graphs of bounded treewidth.
Cite as

Maria Chudnovsky, David Eppstein, and David Fischer. String Graph Obstacles of High Girth and of Bounded Degree. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chudnovsky_et_al:LIPIcs.GD.2025.24,
  author =	{Chudnovsky, Maria and Eppstein, David and Fischer, David},
  title =	{{String Graph Obstacles of High Girth and of Bounded Degree}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.24},
  URN =		{urn:nbn:de:0030-drops-250108},
  doi =		{10.4230/LIPIcs.GD.2025.24},
  annote =	{Keywords: string graphs, induced minors, forbidden minors, sparsity, triangle-free graphs, near-planar graphs}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.17
Visualizing Treewidth

Authors: Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag, and with "tracks" for each graph vertex connecting its copies in multiple bags. Within bags, we optimize the vertex layout to avoid crossings of edges and tracks. We implement a visualization prototype for crossing minimization using dynamic programming for graphs of small width and heuristic approaches for graphs of larger width. We introduce a taxonomy of drawing styles, which render the subgraph for each bag as an arc diagram with one or two pages or as a circular layout with straight-line edges, and we render tracks either with straight lines or with orbital-radial paths.
Cite as

Alvin Chiu, Thomas Depian, David Eppstein, Michael T. Goodrich, and Martin Nöllenburg. Visualizing Treewidth. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chiu_et_al:LIPIcs.GD.2025.17,
  author =	{Chiu, Alvin and Depian, Thomas and Eppstein, David and Goodrich, Michael T. and N\"{o}llenburg, Martin},
  title =	{{Visualizing Treewidth}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.17},
  URN =		{urn:nbn:de:0030-drops-250034},
  doi =		{10.4230/LIPIcs.GD.2025.17},
  annote =	{Keywords: Graph drawing, witness drawings, pathwidth, treewidth}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.39
Optimizing Wiggle in Storylines

Authors: Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A storyline visualization shows interactions between characters over time. Each character is represented by an x-monotone curve. Time is mapped to the x-axis, and groups of characters that interact at a particular point t in time must be ordered consecutively in the y-dimension at x = t. The predominant objective in storyline optimization so far has been the minimization of crossings between (blocks of) characters. Building on this work, we investigate another important, but less studied quality criterion, namely the minimization of wiggle, i.e., the amount of vertical movement of the characters over time. Given a storyline instance together with an ordering of the characters at any point in time, we show that wiggle count minimization is NP-complete. In contrast, we provide algorithms based on mathematical programming to solve linear wiggle height minimization and quadratic wiggle height minimization efficiently. Finally, we introduce a new method for routing character curves that focuses on keeping distances between neighboring curves constant as long as they run in parallel. We have implemented our algorithms, and we conduct a case study that explores the differences between the three optimization objectives. We use existing benchmark data, but we also present a new use case for storylines, namely the visualization of rolling stock schedules in railway operation.
Cite as

Alexander Dobler, Tim Hegemann, Martin Nöllenburg, and Alexander Wolff. Optimizing Wiggle in Storylines. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dobler_et_al:LIPIcs.GD.2025.39,
  author =	{Dobler, Alexander and Hegemann, Tim and N\"{o}llenburg, Martin and Wolff, Alexander},
  title =	{{Optimizing Wiggle in Storylines}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{39:1--39:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.39},
  URN =		{urn:nbn:de:0030-drops-250252},
  doi =		{10.4230/LIPIcs.GD.2025.39},
  annote =	{Keywords: Storyline visualization, wiggle minimization, NP-complete, linear programming, quadratic programming, experimental analysis}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.29
Stabbing Faces by a Convex Curve

Authors: David Eppstein

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We prove that, for every plane graph G and every smooth convex curve C not on a single line, there exists a straight-line drawing of G for which every face is crossed by C.
Cite as

David Eppstein. Stabbing Faces by a Convex Curve. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 29:1-29:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.GD.2025.29,
  author =	{Eppstein, David},
  title =	{{Stabbing Faces by a Convex Curve}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{29:1--29:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.29},
  URN =		{urn:nbn:de:0030-drops-250155},
  doi =		{10.4230/LIPIcs.GD.2025.29},
  annote =	{Keywords: planar graphs, convex curves, stabbing, transversal}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.7
Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii

Authors: Sayan Bandyapadhyay and Eli Mitchell

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We study the Discrete Covering with Two Types of Radii problem motivated by its application in wireless networks. In this problem, the goal is to assign either small-range high frequency or large-range low frequency to each access point, maximizing the number of users in high-frequency regions while ensuring that each user is in the range of an access point. Unlike other weighted covering problems, our problem requires satisfying two simultaneous objectives, which calls for novel approaches that leverage the underlying geometry of the problem. In our work, we present two new algorithms: the first is a polynomial-time (2.5 + ε)-approximation, and the second is an exact algorithm for sparse instances, which is fixed-parameter tractable (FPT) in the number of large-radius disks. We also prove that such an FPT algorithm is impossible for general instances lacking sparsity, assuming the Exponential Time Hypothesis. Before our work, the best-known polynomial-time approximation factor was 4 for the problem. Our approximation algorithm results from a fine-grained classification of points that can contribute to the gain of a solution. Based on this classification, we design two sub-algorithms with interdependent guarantees to recover the respective class of points as gain. Our algorithm exploits further properties of Delaunay triangulations to achieve the improved bound. The FPT algorithm is based on branching that utilizes the sparsity of the instances to limit the overall search space.
Cite as

Sayan Bandyapadhyay and Eli Mitchell. Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bandyapadhyay_et_al:LIPIcs.WADS.2025.7,
  author =	{Bandyapadhyay, Sayan and Mitchell, Eli},
  title =	{{Approximation and Parameterized Algorithms for Covering with Disks of Two Types of Radii}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.7},
  URN =		{urn:nbn:de:0030-drops-242386},
  doi =		{10.4230/LIPIcs.WADS.2025.7},
  annote =	{Keywords: Covering, Disks, Approximation, FPT}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.17
Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
In their seminal work, Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010] showed that a wide class of geometric set cover (SC) problems admit a PTAS via local search - this is one of the most general approaches known for such problems. Their result applies if a naturally defined "exchange graph" for two feasible solutions is planar and is based on subdividing this graph via a planar separator theorem due to Frederickson [Greg N. Frederickson, 1987]. Obtaining similar results for the related maximum coverage problem (MC) seems non-trivial due to the hard cardinality constraint. In fact, while Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] have shown (via a different analysis) that local search yields a PTAS for two-dimensional real halfspaces, they only conjectured that the same holds true for dimension three. Interestingly, at this point it was already known that local search provides a PTAS for the corresponding set cover case and this followed directly from the approach of Mustafa and Ray. In this work we provide a way to address the above-mentioned issue. First, we propose a color-balanced version of the planar separator theorem. The resulting subdivision approximates locally in each part the global distribution of the colors. Second, we show how this roughly balanced subdivision can be employed in a more careful analysis to strictly obey the hard cardinality constraint. More specifically, we obtain a PTAS for any "planarizable" instance of MC and thus essentially for all cases where the corresponding SC instance can be tackled via the approach of Mustafa and Ray. As a corollary, we confirm the conjecture of Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding real halfspaces in dimension three. We feel that our ideas could also be helpful in other geometric settings involving a cardinality constraint.
Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Approximation Schemes for Geometric Coverage Problems. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ESA.2018.17,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.17},
  URN =		{urn:nbn:de:0030-drops-94809},
  doi =		{10.4230/LIPIcs.ESA.2018.17},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.ICALP.2018.107
Brief Announcement: Approximation Schemes for Geometric Coverage Problems

Authors: Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In this announcement, we show that the classical Maximum Coverage problem (MC) admits a PTAS via local search in essentially all cases where the corresponding instances of Set Cover (SC) admit a PTAS via the local search approach by Mustafa and Ray [Nabil H. Mustafa and Saurabh Ray, 2010]. As a corollary, we answer an open question by Badanidiyuru, Kleinberg, and Lee [Ashwinkumar Badanidiyuru et al., 2012] regarding half-spaces in R^3 thereby settling the existence of PTASs for essentially all natural cases of geometric MC problems. As an intermediate result, we show a color-balanced version of the classical planar subdivision theorem by Frederickson [Greg N. Frederickson, 1987]. We believe that some of our ideas may be useful for analyzing local search in other settings involving a hard cardinality constraint.
Cite as

Steven Chaplick, Minati De, Alexander Ravsky, and Joachim Spoerhase. Brief Announcement: Approximation Schemes for Geometric Coverage Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 107:1-107:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaplick_et_al:LIPIcs.ICALP.2018.107,
  author =	{Chaplick, Steven and De, Minati and Ravsky, Alexander and Spoerhase, Joachim},
  title =	{{Brief Announcement: Approximation Schemes for Geometric Coverage Problems}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{107:1--107:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.107},
  URN =		{urn:nbn:de:0030-drops-91113},
  doi =		{10.4230/LIPIcs.ICALP.2018.107},
  annote =	{Keywords: balanced separators, maximum coverage, local search, approximation scheme, geometric approximation algorithms}
}
  • Refine by Type
  • 7 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 2 2018

  • Refine by Author
  • 3 Eppstein, David
  • 2 Chaplick, Steven
  • 2 De, Minati
  • 2 Nöllenburg, Martin
  • 2 Ravsky, Alexander
  • Show More...

  • Refine by Series/Journal
  • 7 LIPIcs

  • Refine by Classification
  • 2 Human-centered computing → Graph drawings
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Packing and covering problems
  • 1 Mathematics of computing → Approximation algorithms
  • 1 Mathematics of computing → Graphs and surfaces
  • Show More...

  • Refine by Keyword
  • 2 approximation scheme
  • 2 balanced separators
  • 2 geometric approximation algorithms
  • 2 local search
  • 2 maximum coverage
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact