Search Results

Documents authored by M. Reddy, Meghana

Document
DOI: 10.4230/LIPIcs.SoCG.2024.18
Plane Hamiltonian Cycles in Convex Drawings

Authors: Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
A conjecture by Rafla from 1988 asserts that every simple drawing of the complete graph K_n admits a plane Hamiltonian cycle. It turned out that already the existence of much simpler non-crossing substructures in such drawings is hard to prove. Recent progress was made by Aichholzer et al. and by Suk and Zeng who proved the existence of a plane path of length Ω(log n / log log n) and of a plane matching of size Ω(n^{1/2}) in every simple drawing of K_n. Instead of studying simpler substructures, we prove Rafla’s conjecture for the subclass of convex drawings, the most general class in the convexity hierarchy introduced by Arroyo et al. Moreover, we show that every convex drawing of K_n contains a plane Hamiltonian path between each pair of vertices (Hamiltonian connectivity) and a plane k-cycle for each 3 ≤ k ≤ n (pancyclicity), and present further results on maximal plane subdrawings.
Cite as

Helena Bergold, Stefan Felsner, Meghana M. Reddy, Joachim Orthaber, and Manfred Scheucher. Plane Hamiltonian Cycles in Convex Drawings. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bergold_et_al:LIPIcs.SoCG.2024.18,
  author =	{Bergold, Helena and Felsner, Stefan and M. Reddy, Meghana and Orthaber, Joachim and Scheucher, Manfred},
  title =	{{Plane Hamiltonian Cycles in Convex Drawings}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.18},
  URN =		{urn:nbn:de:0030-drops-199630},
  doi =		{10.4230/LIPIcs.SoCG.2024.18},
  annote =	{Keywords: simple drawing, convexity hierarchy, plane pancyclicity, plane Hamiltonian connectivity, maximal plane subdrawing}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.24
Optimizing Symbol Visibility Through Displacement

Authors: Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
In information visualization, the position of symbols often encodes associated data values. When visualizing data elements with both a numerical and a categorical dimension, positioning in the categorical axis admits some flexibility. This flexibility can be exploited to reduce symbol overlap, and thereby increase legibility. In this paper we initialize the algorithmic study of optimizing symbol legibility via a limited displacement of the symbols. Specifically, we consider unit square symbols that need to be placed at specified y-coordinates. We optimize the drawing order of the symbols as well as their x-displacement, constrained within a rectangular container, to maximize the minimum visible perimeter over all squares. If the container has width and height at most 2, there is a point that stabs all squares. In this case, we prove that a staircase layout is arbitrarily close to optimality and can be computed in O(nlog n) time. If the width is at most 2, there is a vertical line that stabs all squares, and in this case, we give a 2-approximation algorithm (assuming fixed container height) that runs in O(nlog n) time. As a minimum visible perimeter of 2 is always trivially achievable, we measure this approximation with respect to the visible perimeter exceeding 2. We show that, despite its simplicity, the algorithm gives asymptotically optimal results for certain instances.
Cite as

Bernd Gärtner, Vishwas Kalani, Meghana M. Reddy, Wouter Meulemans, Bettina Speckmann, and Miloš Stojaković. Optimizing Symbol Visibility Through Displacement. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 24:1-24:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{gartner_et_al:LIPIcs.SWAT.2024.24,
  author =	{G\"{a}rtner, Bernd and Kalani, Vishwas and M. Reddy, Meghana and Meulemans, Wouter and Speckmann, Bettina and Stojakovi\'{c}, Milo\v{s}},
  title =	{{Optimizing Symbol Visibility Through Displacement}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{24:1--24:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.24},
  URN =		{urn:nbn:de:0030-drops-200643},
  doi =		{10.4230/LIPIcs.SWAT.2024.24},
  annote =	{Keywords: symbol placement, visibility, jittering, stacking order}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.39
The Number of Edges in Maximal 2-Planar Graphs

Authors: Michael Hoffmann and Meghana M. Reddy

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
A graph is 2-planar if it has local crossing number two, that is, it can be drawn in the plane such that every edge has at most two crossings. A graph is maximal 2-planar if no edge can be added such that the resulting graph remains 2-planar. A 2-planar graph on n vertices has at most 5n-10 edges, and some (maximal) 2-planar graphs - referred to as optimal 2-planar - achieve this bound. However, in strong contrast to maximal planar graphs, a maximal 2-planar graph may have fewer than the maximum possible number of edges. In this paper, we determine the minimum edge density of maximal 2-planar graphs by proving that every maximal 2-planar graph on n ≥ 5 vertices has at least 2n edges. We also show that this bound is tight, up to an additive constant. The lower bound is based on an analysis of the degree distribution in specific classes of drawings of the graph. The upper bound construction is verified by carefully exploring the space of admissible drawings using computer support.
Cite as

Michael Hoffmann and Meghana M. Reddy. The Number of Edges in Maximal 2-Planar Graphs. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{hoffmann_et_al:LIPIcs.SoCG.2023.39,
  author =	{Hoffmann, Michael and M. Reddy, Meghana},
  title =	{{The Number of Edges in Maximal 2-Planar Graphs}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.39},
  URN =		{urn:nbn:de:0030-drops-178894},
  doi =		{10.4230/LIPIcs.SoCG.2023.39},
  annote =	{Keywords: k-planar graphs, local crossing number, saturated graphs, beyond-planar graphs}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2022.17
Lions and Contamination: Monotone Clearings

Authors: Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann

Published in: LIPIcs, Volume 227, 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)

Abstract
We consider a special variant of a pursuit-evasion game called lions and contamination. In a graph whose vertices are originally contaminated, a set of lions walk around the graph and clear the contamination from every vertex they visit. The contamination, however, simultaneously spreads to any adjacent vertex not occupied by a lion. We study the relationship between different types of clearings of graphs, such as clearings which do not allow recontamination, clearings where at most one lion moves at each time step and clearings where lions are forbidden to be stacked on the same vertex. We answer several questions raised by Adams et al. [H. Adams et al., 2020].
Cite as

Daniel Bertschinger, Meghana M. Reddy, and Enrico Mann. Lions and Contamination: Monotone Clearings. In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 227, pp. 17:1-17:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bertschinger_et_al:LIPIcs.SWAT.2022.17,
  author =	{Bertschinger, Daniel and M. Reddy, Meghana and Mann, Enrico},
  title =	{{Lions and Contamination: Monotone Clearings}},
  booktitle =	{18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2022)},
  pages =	{17:1--17:11},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-236-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{227},
  editor =	{Czumaj, Artur and Xin, Qin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2022.17},
  URN =		{urn:nbn:de:0030-drops-161778},
  doi =		{10.4230/LIPIcs.SWAT.2022.17},
  annote =	{Keywords: Algorithmic Games, Pursuit-Evasion Games, Graph Contamination, Clearings}
}
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact