Document

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

A range family ℛ is a family of subsets of ℝ^d, like all halfplanes, or all unit disks. Given a range family ℛ, we consider the m-uniform range capturing hypergraphs ℋ(V,ℛ,m) whose vertex-sets V are finite sets of points in ℝ^d with any m vertices forming a hyperedge e whenever e = V ∩ R for some R ∈ ℛ. Given additionally an integer k ≥ 2, we seek to find the minimum m = m_ℛ(k) such that every ℋ(V,ℛ,m) admits a polychromatic k-coloring of its vertices, that is, where every hyperedge contains at least one point of each color. Clearly, m_ℛ(k) ≥ k and the gold standard is an upper bound m_ℛ(k) = O(k) that is linear in k.
A t-shallow hitting set in ℋ(V,ℛ,m) is a subset S ⊆ V such that 1 ≤ |e ∩ S| ≤ t for each hyperedge e; i.e., every hyperedge is hit at least once but at most t times by S. We show for several range families ℛ the existence of t-shallow hitting sets in every ℋ(V,ℛ,m) with t being a constant only depending on ℛ. This in particular proves that m_ℛ(k) ≤ tk = O(k) in such cases, improving previous polynomial bounds in k. Particularly, we prove this for the range families of all axis-aligned strips in ℝ^d, all bottomless and topless rectangles in ℝ², and for all unit-height axis-aligned rectangles in ℝ².

Tim Planken and Torsten Ueckerdt. Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{planken_et_al:LIPIcs.SoCG.2024.74, author = {Planken, Tim and Ueckerdt, Torsten}, title = {{Polychromatic Colorings of Geometric Hypergraphs via Shallow Hitting Sets}}, booktitle = {40th International Symposium on Computational Geometry (SoCG 2024)}, pages = {74:1--74:14}, 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.74}, URN = {urn:nbn:de:0030-drops-200199}, doi = {10.4230/LIPIcs.SoCG.2024.74}, annote = {Keywords: geometric hypergraphs, range spaces, polychromatic coloring, shallow hitting sets} }

Document

**Published in:** LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

A RAC graph is one admitting a RAC drawing, that is, a polyline drawing in which each crossing occurs at a right angle. Originally motivated by psychological studies on readability of graph layouts, RAC graphs form one of the most prominent graph classes in beyond planarity.
In this work, we study a subclass of RAC graphs, called axis-parallel RAC (or apRAC, for short), that restricts the crossings to pairs of axis-parallel edge-segments. apRAC drawings combine the readability of planar drawings with the clarity of (non-planar) orthogonal drawings. We consider these graphs both with and without bends. Our contribution is as follows: (i) We study inclusion relationships between apRAC and traditional RAC graphs. (ii) We establish bounds on the edge density of apRAC graphs. (iii) We show that every graph with maximum degree 8 is 2-bend apRAC and give a linear time drawing algorithm. Some of our results on apRAC graphs also improve the state of the art for general RAC graphs. We conclude our work with a list of open questions and a discussion of a natural generalization of the apRAC model.

Patrizio Angelini, Michael A. Bekos, Julia Katheder, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Axis-Parallel Right Angle Crossing Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 9:1-9:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.ESA.2023.9, author = {Angelini, Patrizio and Bekos, Michael A. and Katheder, Julia and Kaufmann, Michael and Pfister, Maximilian and Ueckerdt, Torsten}, title = {{Axis-Parallel Right Angle Crossing Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {9:1--9:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.9}, URN = {urn:nbn:de:0030-drops-186623}, doi = {10.4230/LIPIcs.ESA.2023.9}, annote = {Keywords: Graph drawing, RAC graphs, Graph drawing algorithms} }

Document

**Published in:** LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

It follows from the work of Tait and the Four-Color-Theorem that a planar cubic graph is 3-edge-colorable if and only if it contains no bridge. We consider the question of which planar graphs are subgraphs of planar cubic bridgeless graphs, and hence 3-edge-colorable. We provide an efficient recognition algorithm that given an n-vertex planar graph, augments this graph in 𝒪(n²) steps to a planar cubic bridgeless supergraph, or decides that no such augmentation is possible. The main tools involve the Generalized (Anti)factor-problem for the fixed embedding case, and SPQR-trees for the variable embedding case.

Miriam Goetze, Paul Jungeblut, and Torsten Ueckerdt. Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{goetze_et_al:LIPIcs.ESA.2022.62, author = {Goetze, Miriam and Jungeblut, Paul and Ueckerdt, Torsten}, title = {{Efficient Recognition of Subgraphs of Planar Cubic Bridgeless Graphs}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {62:1--62:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.62}, URN = {urn:nbn:de:0030-drops-170007}, doi = {10.4230/LIPIcs.ESA.2022.62}, annote = {Keywords: edge colorings, planar graphs, cubic graphs, generalized factors, SPQR-tree} }

Document

**Published in:** LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Two boxes in ℝ^d are comparable if one of them is a subset of a translation of the other one. The comparable box dimension of a graph G is the minimum integer d such that G can be represented as a touching graph of comparable axis-aligned boxes in ℝ^d. We show that proper minor-closed classes have bounded comparable box dimension and explore further properties of this notion.

Zdeněk Dvořák, Daniel Gonçalves, Abhiruk Lahiri, Jane Tan, and Torsten Ueckerdt. On Comparable Box Dimension. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 38:1-38:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.38, author = {Dvo\v{r}\'{a}k, Zden\v{e}k and Gon\c{c}alves, Daniel and Lahiri, Abhiruk and Tan, Jane and Ueckerdt, Torsten}, title = {{On Comparable Box Dimension}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {38:1--38:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.38}, URN = {urn:nbn:de:0030-drops-160461}, doi = {10.4230/LIPIcs.SoCG.2022.38}, annote = {Keywords: geometric graphs, minor-closed graph classes, treewidth fragility} }

Document

**Published in:** LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Weak and strong coloring numbers are generalizations of the degeneracy of a graph, where for a positive integer k, we seek a vertex ordering such that every vertex can (weakly respectively strongly) reach in k steps only few vertices that precede it in the ordering. Both notions capture the sparsity of a graph or a graph class, and have interesting applications in structural and algorithmic graph theory. Recently, Dvořák, McCarty, and Norin observed a natural volume-based upper bound for the strong coloring numbers of intersection graphs of well-behaved objects in ℝ^d, such as homothets of a compact convex object, or comparable axis-aligned boxes.
In this paper, we prove upper and lower bounds for the k-th weak coloring numbers of these classes of intersection graphs. As a consequence, we describe a natural graph class whose strong coloring numbers are polynomial in k, but the weak coloring numbers are exponential. We also observe a surprising difference in terms of the dependence of the weak coloring numbers on the dimension between touching graphs of balls (single-exponential) and hypercubes (double-exponential).

Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, and Yelena Yuditsky. Weak Coloring Numbers of Intersection Graphs. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.SoCG.2022.39, author = {Dvo\v{r}\'{a}k, Zden\v{e}k and Pek\'{a}rek, Jakub and Ueckerdt, Torsten and Yuditsky, Yelena}, title = {{Weak Coloring Numbers of Intersection Graphs}}, booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-227-3}, ISSN = {1868-8969}, year = {2022}, volume = {224}, editor = {Goaoc, Xavier and Kerber, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.39}, URN = {urn:nbn:de:0030-drops-160477}, doi = {10.4230/LIPIcs.SoCG.2022.39}, annote = {Keywords: geometric intersection graphs, weak and strong coloring numbers} }

Document

**Published in:** LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)

In a wind farm turbines convert wind energy into electrical energy. The generation of each turbine is transmitted, possibly via other turbines, to a substation that is connected to the power grid. On every possible interconnection there can be at most one of various different cable types. Each cable type comes with a cost per unit length and with a capacity. Designing a cost-minimal cable layout for a wind farm to feed all turbine production into the power grid is called the Wind Farm Cabling Problem (WCP).
We consider a formulation of WCP as a flow problem on a graph where the cost of a flow on an edge is modeled by a step function originating from the cable types. Recently, we presented a proof-of-concept for a negative cycle canceling-based algorithm for WCP [Sascha Gritzbach et al., 2018]. We extend key steps of that heuristic and build a theoretical foundation that explains how this heuristic tackles the problems arising from the special structure of WCP.
A thorough experimental evaluation identifies the best setup of the algorithm and compares it to existing methods from the literature such as Mixed-integer Linear Programming (MILP) and Simulated Annealing (SA). The heuristic runs in a range of half a millisecond to under two minutes on instances with up to 500 turbines. It provides solutions of similar quality compared to both competitors with running times of one hour and one day. When comparing the solution quality after a running time of two seconds, our algorithm outperforms the MILP- and SA-approaches, which allows it to be applied in interactive wind farm planning.

Sascha Gritzbach, Torsten Ueckerdt, Dorothea Wagner, Franziska Wegner, and Matthias Wolf. Engineering Negative Cycle Canceling for Wind Farm Cabling. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gritzbach_et_al:LIPIcs.ESA.2019.55, author = {Gritzbach, Sascha and Ueckerdt, Torsten and Wagner, Dorothea and Wegner, Franziska and Wolf, Matthias}, title = {{Engineering Negative Cycle Canceling for Wind Farm Cabling}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {55:1--55:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola 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.2019.55}, URN = {urn:nbn:de:0030-drops-111766}, doi = {10.4230/LIPIcs.ESA.2019.55}, annote = {Keywords: Negative Cycle Canceling, Step Cost Function, Wind Farm Planning} }

Document

**Published in:** LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)

Beyond-planarity focuses on the study of geometric and topological graphs that are in some sense nearly planar. Here, planarity is relaxed by allowing edge crossings, but only with respect to some local forbidden crossing configurations. Early research dates back to the 1960s (e.g., Avital and Hanani 1966) for extremal problems on geometric graphs, but is also related to graph drawing problems where visual clutter due to edge crossings should be minimized (e.g., Huang et al. 2018).
Most of the literature focuses on Turán-type problems, which ask for the maximum number of edges a beyond-planar graph can have. Here, we study this problem for bipartite topological graphs, considering several types of beyond-planar graphs, i.e. 1-planar, 2-planar, fan-planar, and RAC graphs. We prove bounds on the number of edges that are tight up to additive constants; some of them are surprising and not along the lines of the known results for non-bipartite graphs. Our findings lead to an improvement of the leading constant of the well-known Crossing Lemma for bipartite graphs, as well as to a number of interesting questions on topological graphs.

Patrizio Angelini, Michael A. Bekos, Michael Kaufmann, Maximilian Pfister, and Torsten Ueckerdt. Beyond-Planarity: Turán-Type Results for Non-Planar Bipartite Graphs. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 28:1-28:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{angelini_et_al:LIPIcs.ISAAC.2018.28, author = {Angelini, Patrizio and Bekos, Michael A. and Kaufmann, Michael and Pfister, Maximilian and Ueckerdt, Torsten}, title = {{Beyond-Planarity: Tur\'{a}n-Type Results for Non-Planar Bipartite Graphs}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {28:1--28:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.28}, URN = {urn:nbn:de:0030-drops-99763}, doi = {10.4230/LIPIcs.ISAAC.2018.28}, annote = {Keywords: Bipartite topological graphs, beyond planarity, density, Crossing Lemma} }

Document

**Published in:** LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

We study on-line colorings of certain graphs given as intersection graphs of objects "between two lines", i.e., there is a pair of horizontal lines such that each object of the representation is a connected set contained in the strip between the lines and touches both. Some of the graph classes admitting such a representation are permutation graphs (segments), interval graphs (axis-aligned rectangles), trapezoid graphs (trapezoids) and cocomparability graphs (simple curves). We present an on-line algorithm coloring graphs given by convex sets between two lines that uses O(w^3) colors on graphs with maximum clique size w.
In contrast intersection graphs of segments attached to a single line may force any on-line coloring algorithm to use an arbitrary number of colors even when w=2.
The left-of relation makes the complement of intersection graphs of objects between two lines into a poset. As an aside we discuss the relation of the class C of posets obtained from convex sets between two lines with some other classes of posets: all 2-dimensional posets and all posets of height 2 are in C but there is a 3-dimensional poset of height 3 that does not belong to C.
We also show that the on-line coloring problem for curves between two lines is as hard as the on-line chain partition problem for arbitrary posets.

Stefan Felsner, Piotr Micek, and Torsten Ueckerdt. On-line Coloring between Two Lines. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 630-641, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SOCG.2015.630, author = {Felsner, Stefan and Micek, Piotr and Ueckerdt, Torsten}, title = {{On-line Coloring between Two Lines}}, booktitle = {31st International Symposium on Computational Geometry (SoCG 2015)}, pages = {630--641}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-83-5}, ISSN = {1868-8969}, year = {2015}, volume = {34}, editor = {Arge, Lars and Pach, J\'{a}nos}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.630}, URN = {urn:nbn:de:0030-drops-50915}, doi = {10.4230/LIPIcs.SOCG.2015.630}, annote = {Keywords: intersection graphs, cocomparability graphs, on-line coloring} }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail