Meghana M. Reddy

I'm currently a Research Engineer at Telepathy Labs, working on AI solutions to improve customer experience. Until February 2024, I was a doctoral student in the Theory of Combinatorial Algorithms group at ETH Zürich, under the supervision of Dr. Michael Hoffmann and Prof. Emo Welzl. I graduated with a Masters in Computer Science from IIIT-Bangalore in July 2018. My Master thesis titled "On the Chromatic Art Gallery Problem" was supervised by Prof. Pradeesha Ashok. I also had the oppurtunity to work with Prof. Saket Saurabh during April-May 2018 at IMSc, Chennai.

My interests lie in Computational Geometry and Graph Theory, mainly topological graph theory and graph drawings. Prior to starting my PhD, I worked at Amazon India as a Software Development Engineer from August 2018 to August 2019. I also contributed to the graph module of SageMath through Google Summer of Code 2018 (a report of the project can be found here).

Contact

News

I no longer have access to my ETH email, I will miss any emails sent to it.
Nov 20, 2023: Successfully defended my doctoral thesis titled "Beyond-Planar Graphs: Simple and Maximal" :)

Publications and Preprints

The Density Formula: One Lemma to Bound Them All

Michael Kaufmann, Boris Klemz, Kristin Knorr, Meghana M. Reddy, Felix Schröder and Torsten Ueckerdt.
GD 2024 (won the Best Paper Award).

Optimizing Symbol Visibility through Displacement

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

Using SAT to study plane Hamiltonian substructures in simple drawings

Helena Bergold, Stefan Felsner, Meghana M. Reddy and Manfred Scheucher.
SoCG 2024

The Number of Edges in Maximal 2-planar Graphs

Michael Hoffmann and Meghana M. Reddy.
SoCG 2023.

Compatible Spanning Trees in Simple Drawings of \(K_n\)

Oswin Aichholzer, Kristin Knorr, Wolfgang Mulzer, Nicolas El Maalouly, Johannes Obenaus, Rosna Paul, Meghana M. Reddy, Birgit Vogtenhuber and Alexandra Weinberger.
GD 2022.

Lions and Contamination: Monotone Clearings

Daniel Bertschinger, Meghana M. Reddy and Enrico Mann.
SWAT 2022 (won the Best Student Paper Award) and CGTA 2023.

Simplifying Non-Simple Fan-Planar Drawings

Boris Klemz, Kristin Knorr, Meghana M. Reddy and Felix Schröder.
GD 2021 and JGAA 2022.

Local Complexity of Polygons

Fabian Klute, Meghana M. Reddy and Tillmann Miltzow.

Simple Topological Drawings of k-Planar Graphs

Michael Hoffmann, Chih-Hung Liu, Meghana M. Reddy and Csaba D. Tóth.
GD 2020.

Efficient Guarding of Polygons and Terrains

Pradeesha Ashok and Meghana M. Reddy.
FAW 2019.

FPT Algorithms for Conflict-free Coloring of Graphs and Chromatic Terrain Guarding

Akanksha Agrawal, Pradeesha Ashok, Meghana M. Reddy, Saket Saurabh and Dolly Yadav.

Research visits

Prof. Wolfgang Mulzer, FU Berlin, Germany, March-April 2022.

Teaching

Geometry: Combinatorics & Algorithms (Head Assistant) (Fall 2023, Fall 2022)
Algorithms Lab (Fall 2023, Fall 2022, Fall 2021)
Algorithmen und Wahrscheinlichkeit (Spring 2021, Spring 2020)
Algorithms, Probability and Computing (Fall 2020)

Talks and seminars

The Density Formula: One Lemma to Bound Them All, Mittagsseminar, ETH Zürich, Switzerland, December 2023.
Local Complexity of Polygons and its Relevance in the Art Gallery Problem, Mittagsseminar, ETH Zürich, Switzerland, April 2023.
The Number of Edges in Maximal 2-planar Graphs, EuroCG 2023, Barcelona, Spain, March 2023.
The Number of Edges in Maximal 2-planar Graphs, Mittagsseminar, ETH Zürich, Switzerland, October 2022.
Lions and Contamination, Mittagsseminar, TU Berlin, March 2022.
Lions and Contamination: Monotone Clearings, EuroCG 2022, Perugia, Italy, March 2022.
Simplifying Non-Simple Fan-Planar Drawings, GD 2021, Tübingen, Germany, September 2021.
Local Complexity of Polygons, EuroCG 2021, April 2021.
Simple Drawings and Straight Line Drawings of k-planar Graphs, Mittagsseminar, ETH Zürich, Switzerland, March 2021.
Topological Drawings meet Classical Theorems from Convex Geometry, Mittagsseminar, ETH Zürich, Switzerland, October 2020.
Simple Topological Drawings of k-Planar Graphs, GD 2020, September 2020.
Simple Topological Drawings of k-Planar Graphs, Mittagsseminar, ETH Zürich, Switzerland, April 2020.
Simple Topological Drawings of k-Planar Graphs, EuroCG 2020, March 2020.

Supervised Theses

[Semester thesis] Shengzhe Wang, Maximal 3-planar Graphs, September 2023, co-supervised with Michael Hoffmann.
[Master thesis] Benjamin O'Sullivan, Edge Operations and Happy Edges, August 2023.
[Master thesis] Emanuel Seemann, Matchings and Hamiltonian Cycles in 1-Planar Graphs, August 2022, co-supervised with Michael Hoffmann.
[Master thesis] Alexandre Krattinger, Edge-Coloring Simple Topological Drawings of the Complete Graph, April 2022, co-supervised with Michael Hoffmann.
[Bachelor thesis] Enrico Mann, Lions and Contamination, February 2022, co-supervised with Daniel Bertschinger.
[Master thesis] Ning Gao, The maximum geometric subgraph problem, September 2021, co-supervised with Nicolas Grelier.
[Semester thesis] Alain Bastian, Edge coloring complete geometric graphs, May 2021, co-supervised with Michael Hoffmann.
[Bachelor thesis] Emanuel Seemann, Monotone topological book embeddings of planar graphs with fixed spinal order, December 2019, co-supervised with Michael Hoffmann.

Updated in October 2024.