5 Search Results for "van Beusekom, Nathan"

Document
DOI: 10.4230/LIPIcs.ESA.2025.21
A Unified FPT Framework for Crossing Number Problems

Authors: Éric Colin de Verdière and Petr Hliněný

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
The basic (and traditional) crossing number problem is to determine the minimum number of crossings in a topological drawing of an input graph in the plane. We develop a unified framework that smoothly captures many generalized crossing number problems, and that yields fixed-parameter tractable (FPT) algorithms for them not only in the plane but also on surfaces. Our framework takes the following form. We fix a surface S, an integer r, and a map κ from the set of topological drawings of graphs in S to ℤ_+ ∪ {∞}, satisfying some natural monotonicity conditions, but essentially describing the allowed drawings and how we want to count the crossings in them. Then deciding whether an input graph G has an allowed drawing D on S with κ(D) ≤ r can be done in time quadratic in the size of G (and exponential in other parameters). More generally, we may take as input an edge-colored graph, and distinguish crossings by the colors of the involved edges; and we may allow to perform a bounded number of edge removals and vertex splits to G before drawing it. The proof is a reduction to the embeddability of a graph on a two-dimensional simplicial complex. This framework implies, in a unified way, quadratic FPT algorithms for many topological crossing number variants established in the graph drawing community. Some of these variants already had previously published FPT algorithms, mostly relying on Courcelle’s metatheorem, but for many of those, we obtain an algorithm with a better runtime. Moreover, our framework extends, at no cost, to these crossing number variants in any fixed surface.
Cite as

Éric Colin de Verdière and Petr Hliněný. A Unified FPT Framework for Crossing Number Problems. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 21:1-21:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{colindeverdiere_et_al:LIPIcs.ESA.2025.21,
  author =	{Colin de Verdi\`{e}re, \'{E}ric and Hlin\v{e}n\'{y}, Petr},
  title =	{{A Unified FPT Framework for Crossing Number Problems}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{21:1--21:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.21},
  URN =		{urn:nbn:de:0030-drops-244897},
  doi =		{10.4230/LIPIcs.ESA.2025.21},
  annote =	{Keywords: computational geometry, fixed-parameter tractability, graph drawing, graph embedding, crossing number, two-dimensional simplicial complex, surface}
}
Document
DOI: 10.4230/LIPIcs.ESA.2025.67
Compact Representation of Semilinear and Terrain-Like Graphs

Authors: Jean Cardinal and Yelena Yuditsky

Published in: LIPIcs, Volume 351, 33rd Annual European Symposium on Algorithms (ESA 2025)

Abstract
We consider the existence and construction of biclique covers of graphs, consisting of coverings of their edge sets by complete bipartite graphs. The size of such a cover is the sum of the sizes of the bicliques. Small-size biclique covers of graphs are ubiquitous in computational geometry, and have been shown to be useful compact representations of graphs. We give a brief survey of classical and recent results on biclique covers and their applications, and give new families of graphs having biclique covers of near-linear size. In particular, we show that semilinear graphs, whose edges are defined by linear relations in bounded dimensional space, always have biclique covers of size O(npolylog n). This generalizes many previously known results on special classes of graphs including interval graphs, permutation graphs, and graphs of bounded boxicity, but also new classes such as intersection graphs of L-shapes in the plane. It also directly implies the bounds for Zarankiewicz’s problem derived by Basit, Chernikov, Starchenko, Tao, and Tran (Forum Math. Sigma, 2021). We also consider capped graphs, also known as terrain-like graphs, defined as ordered graphs forbidding a certain ordered pattern on four vertices. Terrain-like graphs contain the induced subgraphs of terrain visibility graphs. We give an elementary proof that these graphs admit biclique partitions of size O(nlog³ n). This provides a simple combinatorial analogue of a classical result from Agarwal, Alon, Aronov, and Suri on polygon visibility graphs (Discrete Comput. Geom. 1994). Finally, we prove that there exists families of unit disk graphs on n vertices that do not admit biclique coverings of size o(n^{4/3}), showing that we are unlikely to improve on Szemerédi-Trotter type incidence bounds for higher-degree semialgebraic graphs.
Cite as

Jean Cardinal and Yelena Yuditsky. Compact Representation of Semilinear and Terrain-Like Graphs. In 33rd Annual European Symposium on Algorithms (ESA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 351, pp. 67:1-67:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cardinal_et_al:LIPIcs.ESA.2025.67,
  author =	{Cardinal, Jean and Yuditsky, Yelena},
  title =	{{Compact Representation of Semilinear and Terrain-Like Graphs}},
  booktitle =	{33rd Annual European Symposium on Algorithms (ESA 2025)},
  pages =	{67:1--67:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-395-9},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{351},
  editor =	{Benoit, Anne and Kaplan, Haim and Wild, Sebastian 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.2025.67},
  URN =		{urn:nbn:de:0030-drops-245359},
  doi =		{10.4230/LIPIcs.ESA.2025.67},
  annote =	{Keywords: Biclique covers, intersection graphs, visibility graphs, Zarankiewicz’s problem}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.33
Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach

Authors: Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner

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

Abstract
Beyond planarity concepts (prominent examples include k-planarity or fan-planarity) apply certain restrictions on the allowed patterns of crossings in drawings. It is natural to ask, how much the number of crossings may increase over the traditional (unrestricted) crossing number. Previous approaches to bound such ratios, e.g. [Markus Chimani et al., 2022; Nathan van Beusekom et al., 2022], require very specialized constructions and arguments for each considered beyond planarity concept, and mostly only yield asymptotically non-tight bounds. We propose a very general proof framework that allows us to obtain asymptotically tight bounds, and where the concept-specific parts of the proof typically boil down to a couple of lines. We show the strength of our approach by giving improved or first bounds for several beyond planarity concepts.
Cite as

Markus Chimani, Torben Donzelmann, Nick Kloster, Melissa Koch, Jan-Jakob Völlering, and Mirko H. Wagner. Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{chimani_et_al:LIPIcs.GD.2024.33,
  author =	{Chimani, Markus and Donzelmann, Torben and Kloster, Nick and Koch, Melissa and V\"{o}llering, Jan-Jakob and Wagner, Mirko H.},
  title =	{{Crossing Numbers of Beyond Planar Graphs Re-Revisited: A Framework Approach}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{33:1--33: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.33},
  URN =		{urn:nbn:de:0030-drops-213175},
  doi =		{10.4230/LIPIcs.GD.2024.33},
  annote =	{Keywords: Beyond planarity, crossing number, crossing ratio, proof framework}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2024.26
Capturing the Shape of a Point Set with a Line Segment

Authors: Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract
Detecting location-correlated groups in point sets is an important task in a wide variety of applications areas. In addition to merely detecting such groups, the group’s shape carries meaning as well. In this paper, we represent a group’s shape using a simple geometric object, a line segment. Specifically, given a radius r, we say a line segment is representative of a point set P of n points if it is within distance r of each point p ∈ P. We aim to find the shortest such line segment. This problem is equivalent to stabbing a set of circles of radius r using the shortest line segment. We describe an algorithm to find the shortest representative segment in O(n log h + h log³h) time, where h is the size of the convex hull of P. Additionally, we show how to maintain a stable approximation of the shortest representative segment when the points in P move.
Cite as

Nathan van Beusekom, Marc van Kreveld, Max van Mulken, Marcel Roeloffzen, Bettina Speckmann, and Jules Wulms. Capturing the Shape of a Point Set with a Line Segment. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 26:1-26:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.MFCS.2024.26,
  author =	{van Beusekom, Nathan and van Kreveld, Marc and van Mulken, Max and Roeloffzen, Marcel and Speckmann, Bettina and Wulms, Jules},
  title =	{{Capturing the Shape of a Point Set with a Line Segment}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{26:1--26:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.26},
  URN =		{urn:nbn:de:0030-drops-205820},
  doi =		{10.4230/LIPIcs.MFCS.2024.26},
  annote =	{Keywords: Shape descriptor, Stabbing, Rotating calipers}
}
Document
DOI: 10.4230/LIPIcs.GIScience.2023.10
Data-Spatial Layouts for Grid Maps

Authors: Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood

Published in: LIPIcs, Volume 277, 12th International Conference on Geographic Information Science (GIScience 2023)

Abstract
Grid maps are a well-known technique to visualize data associated with spatial regions. A grid map assigns each region to a tile in a grid (often orthogonal or hexagonal) and then represents the associated data values within this tile. Good grid maps represent the underlying geographic space well: regions that are geographically close are close in the grid map and vice versa. Though Tobler’s law suggests that spatial proximity relates to data similarity, local variations may obscure clusters and patterns in the data. For example, there are often clear differences between urban centers and adjacent rural areas with respect to socio-economic indicators. To get a better view of the data distribution, we propose grid-map layouts that take data values into account and place regions with similar data into close proximity. In the limit, such a data layout is essentially a chart and loses all spatial meaning. We present an algorithm to create hybrid layouts, allowing for trade-offs between data values and geographic space when assigning regions to tiles. Our algorithm also handles hierarchical grid maps and allows us to focus either on data or on geographic space on different levels of the hierarchy. Leveraging our algorithm we explore the design space of (hierarchical) grid maps with a hybrid layout and their semantics.
Cite as

Nathan van Beusekom, Wouter Meulemans, Bettina Speckmann, and Jo Wood. Data-Spatial Layouts for Grid Maps. In 12th International Conference on Geographic Information Science (GIScience 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 277, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{vanbeusekom_et_al:LIPIcs.GIScience.2023.10,
  author =	{van Beusekom, Nathan and Meulemans, Wouter and Speckmann, Bettina and Wood, Jo},
  title =	{{Data-Spatial Layouts for Grid Maps}},
  booktitle =	{12th International Conference on Geographic Information Science (GIScience 2023)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-288-4},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{277},
  editor =	{Beecham, Roger and Long, Jed A. and Smith, Dianna and Zhao, Qunshan and Wise, Sarah},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GIScience.2023.10},
  URN =		{urn:nbn:de:0030-drops-189052},
  doi =		{10.4230/LIPIcs.GIScience.2023.10},
  annote =	{Keywords: Grid map, algorithms, trade-offs}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 2 2024
  • 1 2023

  • Refine by Author
  • 2 Speckmann, Bettina
  • 2 van Beusekom, Nathan
  • 1 Cardinal, Jean
  • 1 Chimani, Markus
  • 1 Colin de Verdière, Éric
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 4 Theory of computation → Computational geometry
  • 2 Mathematics of computing → Graph theory
  • 1 Theory of computation → Fixed parameter tractability
  • 1 Theory of computation → Graph algorithms analysis

  • Refine by Keyword
  • 2 crossing number
  • 1 Beyond planarity
  • 1 Biclique covers
  • 1 Grid map
  • 1 Rotating calipers
  • 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