DROPS

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2026.97

"Visualizing" the CG Community (Media Exposition)

Authors: Oswin Aichholzer, Hugo A. Akitaya, Anna Brötzner, Peter Kramer, Christian Rieck, and Frederick Stock

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract

We analyze and visualize collaboration within the Computational Geometry community by modeling co-authorship relations as a graph, where nodes correspond to individual researchers and edges represent shared publications. By aggregating and time-slicing conference data, we construct a dynamic representation of the community that supports both interactive visualization and structured search.

Cite as

Oswin Aichholzer, Hugo A. Akitaya, Anna Brötzner, Peter Kramer, Christian Rieck, and Frederick Stock. "Visualizing" the CG Community (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 97:1-97:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.SoCG.2026.97,
  author =	{Aichholzer, Oswin and A. Akitaya, Hugo and Br\"{o}tzner, Anna and Kramer, Peter and Rieck, Christian and Stock, Frederick},
  title =	{{"Visualizing" the CG Community}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{97:1--97:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.97},
  URN =		{urn:nbn:de:0030-drops-259039},
  doi =		{10.4230/LIPIcs.SoCG.2026.97},
  annote =	{Keywords: CG community, visualization, graph parameters, web application}
}

Document

DOI: 10.4230/LIPIcs.WADS.2025.11

Crossing and Independent Families Among Polygons

Authors: Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, and Irene Parada

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

Abstract

Given a set A of points in the plane, a family of line segments forming a matching in A is called crossing (or independent) if each pair of segments in the family intersects (or is non-intersecting, respectively). In past works, these notions have been generalized to polygons by identifying the points in A with the vertices of a given set of polygons and forbidding the line segments from intersecting or overlapping with polygon walls. In this work, we study the computational complexity of computing maximum crossing and independent families in this more general setting. As our first two results, we show that both problems are NP-hard already when the polygons are triangles. Motivated by this, we turn to parameterized algorithms. For our main algorithmic results, we consider the number of polygons on the input as the natural parameter and under this parameterization obtain a fixed-parameter algorithm for computing a largest crossing family among these polygons, and a separate XP-algorithm for computing a largest independent family that lies in one of the faces of the polygonal domain.

Cite as

Anna Brötzner, Robert Ganian, Thekla Hamm, Fabian Klute, and Irene Parada. Crossing and Independent Families Among Polygons. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brotzner_et_al:LIPIcs.WADS.2025.11,
  author =	{Br\"{o}tzner, Anna and Ganian, Robert and Hamm, Thekla and Klute, Fabian and Parada, Irene},
  title =	{{Crossing and Independent Families Among Polygons}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{11:1--11:15},
  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.11},
  URN =		{urn:nbn:de:0030-drops-242424},
  doi =		{10.4230/LIPIcs.WADS.2025.11},
  annote =	{Keywords: crossing families, crossing-free matchings, segment intersection graphs, computational geometry, parameterized algorithms}
}

Search Results

Documents authored by Brötzner, Anna

"Visualizing" the CG Community (Media Exposition)

Abstract

Cite as

Crossing and Independent Families Among Polygons

Abstract

Cite as

Thanks for your feedback!

Could not send message