12 Search Results for "Klemz, Boris"

Document
DOI: 10.4230/LIPIcs.GD.2025.19
Crossing and Non-Crossing Families

Authors: Todor Antić, Martin Balko, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
For a finite set P of points in the plane in general position, a crossing family of size k in P is a collection of k line segments with endpoints in P that are pairwise crossing. It is a long-standing open problem to determine the largest size of a crossing family in any set of n points in the plane in general position. It is widely believed that this size should be linear in n. Motivated by results from the theory of partitioning complete geometric graphs, we study a variant of this problem for point sets P that do not contain a non-crossing family of size m, which is a collection of 4 disjoint subsets P₁, P₂, P₃, and P₄ of P, each containing m points of P, such that for every choice of 4 points p_i ∈ P_i, the set {p₁,p₂,p₃,p₄} is such that p₄ is in the interior of the triangle formed by p₁,p₂,p₃. We prove that, for every m ∈ ℕ, each set P of n points in the plane in general position contains either a crossing family of size n/2^{O(√{log{m}})} or a non-crossing family of size m, by this strengthening a recent breakthrough result by Pach, Rubin, and Tardos (2021). Our proof is constructive and we show that these families can be obtained in expected time O(nm^{1+o(1)}). We also prove that a crossing family of size Ω(n/m) or a non-crossing family of size m in P can be found in expected time O(n).
Cite as

Todor Antić, Martin Balko, and Birgit Vogtenhuber. Crossing and Non-Crossing Families. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 19:1-19:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antic_et_al:LIPIcs.GD.2025.19,
  author =	{Anti\'{c}, Todor and Balko, Martin and Vogtenhuber, Birgit},
  title =	{{Crossing and Non-Crossing Families}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{19:1--19:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.19},
  URN =		{urn:nbn:de:0030-drops-250058},
  doi =		{10.4230/LIPIcs.GD.2025.19},
  annote =	{Keywords: crossing family, non-crossing family, geometric graph}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.33
Edge Densities of Drawings of Graphs with One Forbidden Cell

Authors: Benedikt Hahn, Torsten Ueckerdt, and Birgit Vogtenhuber

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A connected topological drawing of a graph divides the plane into a number of cells. The type of a cell c is the cyclic sequence of crossings and vertices along the boundary walk of c. For example, all triangular cells with three incident crossings and no incident vertex share the same cell type. When a non-homotopic drawing of an n-vertex multigraph G does not contain any such cells, Ackerman and Tardos [JCTA 2007] proved that G has at most 8n-20 edges, while Kaufmann, Klemz, Knorr, Reddy, Schröder, and Ueckerdt [GD 2024] showed that this bound is tight. In this paper, we initiate the in-depth study of non-homotopic drawings that do not contain one fixed cell type 𝔠, and investigate the edge density of the corresponding multigraphs, i.e., the maximum possible number of edges. We consider non-homotopic as well as simple drawings, multigraphs as well as simple graphs, and every possible type of cell. For every combination of drawing style, graph type, and cell type, we give upper and lower bounds on the corresponding edge density. With the exception of the cell type with four incident crossings and no incident vertex, we show for every cell type 𝔠 that the edge density of n-vertex (multi)graphs with 𝔠-free drawings is either quadratic in n or linear in n. In most cases, our bounds are tight up to an additive constant. Additionally, we improve the current lower bound on the edge density of simple graphs that admit a non-homotopic quasiplanar drawing from 7n-28 to 7.5n-28.
Cite as

Benedikt Hahn, Torsten Ueckerdt, and Birgit Vogtenhuber. Edge Densities of Drawings of Graphs with One Forbidden Cell. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hahn_et_al:LIPIcs.GD.2025.33,
  author =	{Hahn, Benedikt and Ueckerdt, Torsten and Vogtenhuber, Birgit},
  title =	{{Edge Densities of Drawings of Graphs with One Forbidden Cell}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.33},
  URN =		{urn:nbn:de:0030-drops-250199},
  doi =		{10.4230/LIPIcs.GD.2025.33},
  annote =	{Keywords: Edge density, cell types, forbidden substructures, non-homotopic drawings, simple drawings}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.63
Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable

Authors: Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza, and Mario Valencia-Pabon

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
An elimination tree of a connected graph G is a rooted tree on the vertices of G obtained by choosing a root v and recursing on the connected components of G-v to obtain the subtrees of v. The graph associahedron of G is a polytope whose vertices correspond to elimination trees of G and whose edges correspond to tree rotations, a natural operation between elimination trees. These objects generalize associahedra, which correspond to the case where G is a path. Ito et al. [ICALP 2023] recently proved that the problem of computing distances on graph associahedra is NP-hard. In this paper we prove that the problem, for a general graph G, is fixed-parameter tractable parameterized by the distance k. Prior to our work, only the case where G is a path was known to be fixed-parameter tractable. To prove our result, we use a novel approach based on a marking scheme that restricts the search to a set of vertices whose size is bounded by a (large) function of k.
Cite as

Luís Felipe I. Cunha, Ignasi Sau, Uéverton S. Souza, and Mario Valencia-Pabon. Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 63:1-63:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cunha_et_al:LIPIcs.ICALP.2025.63,
  author =	{Cunha, Lu{\'\i}s Felipe I. and Sau, Ignasi and Souza, U\'{e}verton S. and Valencia-Pabon, Mario},
  title =	{{Computing Distances on Graph Associahedra Is Fixed-Parameter Tractable}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{63:1--63:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.63},
  URN =		{urn:nbn:de:0030-drops-234408},
  doi =		{10.4230/LIPIcs.ICALP.2025.63},
  annote =	{Keywords: graph associahedra, elimination tree, rotation distance, parameterized complexity, fixed-parameter tractable algorithm, combinatorial shortest path, reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.47
Shelling and Sinking Graphs on the Sphere

Authors: Jeff Erickson and Christian Howard

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
We describe a promising approach to efficiently morph spherical graphs, extending earlier approaches of Awartani and Henderson [Trans. AMS 1987] and Kobourov and Landis [JGAA 2006]. Specifically, we describe two methods to morph shortest-path triangulations of the sphere by moving their vertices along longitudes into the southern hemisphere; we call a triangulation sinkable if such a morph exists. Our first method generalizes a longitudinal shelling construction of Awartani and Henderson; a triangulation is sinkable if a specific orientation of its dual graph is acyclic. We describe a simple polynomial-time algorithm to find a longitudinally shellable rotation of a given spherical triangulation, if one exists; we also construct a spherical triangulation that has no longitudinally shellable rotation. Our second method is based on a linear-programming characterization of sinkability. By identifying its optimal basis, we show that this linear program can be solved in O(n^{ω/2}) time, where ω is the matrix-multiplication exponent, assuming the underlying linear system is non-singular. Finally, we pose several conjectures and describe experimental results that support them.
Cite as

Jeff Erickson and Christian Howard. Shelling and Sinking Graphs on the Sphere. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 47:1-47:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{erickson_et_al:LIPIcs.SoCG.2025.47,
  author =	{Erickson, Jeff and Howard, Christian},
  title =	{{Shelling and Sinking Graphs on the Sphere}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{47:1--47:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.47},
  URN =		{urn:nbn:de:0030-drops-231996},
  doi =		{10.4230/LIPIcs.SoCG.2025.47},
  annote =	{Keywords: morphing, planar graphs, spherical graph drawing, longitudinal shelling}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.65
Recognizing 2-Layer and Outer k-Planar Graphs

Authors: Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The crossing number of a graph is the least number of crossings over all drawings of the graph in the plane. Computing the crossing number of a given graph is NP-hard, but fixed-parameter tractable (FPT) with respect to the natural parameter. Two well-known variants of the problem are 2-layer crossing minimization and circular crossing minimization, where every vertex must lie on one of two layers, namely two parallel lines, or a circle, respectively. In both cases, edges are drawn as straight-line segments. Both variants are NP-hard, but admit FPT-algorithms with respect to the natural parameter. In recent years, in the context of beyond-planar graphs, a local version of the crossing number has also received considerable attention. A graph is k-planar if it admits a drawing with at most k crossings per edge. In contrast to the crossing number, recognizing k-planar graphs is NP-hard even if k = 1 and hence not likely to be FPT with respect to the natural parameter k. In this paper, we consider the two above variants in the local setting. The k-planar graphs that admit a straight-line drawing with vertices on two layers or on a circle are called 2-layer k-planar and outer k-planar graphs, respectively. We study the parameterized complexity of the two recognition problems with respect to the natural parameter k. For k = 0, the two classes of graphs are exactly the caterpillars and outerplanar graphs, respectively, which can be recognized in linear time. Two groups of researchers independently showed that outer 1-planar graphs can also be recognized in linear time [Hong et al., Algorithmica 2015; Auer et al., Algorithmica 2016]. One group asked explicitly whether outer 2-planar graphs can be recognized in polynomial time. Our main contribution consists of XP-algorithms for recognizing 2-layer k-planar graphs and outer k-planar graphs, which implies that both recognition problems can be solved in polynomial time for every fixed k. We complement these results by showing that recognizing 2-layer k-planar graphs is XNLP-complete and that recognizing outer k-planar graphs is XNLP-hard. This implies that both problems are W[t]-hard for every t and that it is unlikely that they admit FPT-algorithms. On the other hand, we present an FPT-algorithm for recognizing 2-layer k-planar graphs where the order of the vertices on one layer is specified.
Cite as

Yasuaki Kobayashi, Yuto Okada, and Alexander Wolff. Recognizing 2-Layer and Outer k-Planar Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 65:1-65:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kobayashi_et_al:LIPIcs.SoCG.2025.65,
  author =	{Kobayashi, Yasuaki and Okada, Yuto and Wolff, Alexander},
  title =	{{Recognizing 2-Layer and Outer k-Planar Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{65:1--65:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.65},
  URN =		{urn:nbn:de:0030-drops-232170},
  doi =		{10.4230/LIPIcs.SoCG.2025.65},
  annote =	{Keywords: 2-layer k-planar graphs, outer k-planar graphs, recognition algorithms, local crossing number, bandwidth, FPT, XNLP, XP, W\lbrackt\rbrack}
}
Document
DOI: 10.4230/LIPIcs.GD.2024.7
The Density Formula: One Lemma to Bound Them All

Authors: Michael Kaufmann, Boris Klemz, Kristin Knorr, Meghana M. Reddy, Felix Schröder, and Torsten Ueckerdt

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

Abstract
We introduce the Density Formula for (topological) drawings of graphs in the plane or on the sphere, which relates the number of edges, vertices, crossings, and sizes of cells in the drawing. We demonstrate its capability by providing several applications: we prove tight upper bounds on the edge density of various beyond-planar graph classes, including so-called k-planar graphs with k = 1,2, fan-crossing/fan-planar graphs, k-bend RAC-graphs with k = 0,1,2, quasiplanar graphs, and k^+-real face graphs. In some cases (1-bend and 2-bend RAC-graphs and fan-crossing/fan-planar graphs), we thereby obtain the first tight upper bounds on the edge density of the respective graph classes. In other cases, we give new streamlined and significantly shorter proofs for bounds that were already known in the literature. Thanks to the Density Formula, all of our proofs are mostly elementary counting and mostly circumvent the typical intricate case analysis found in earlier proofs. Further, in some cases (simple and non-homotopic quasiplanar graphs), our alternative proofs using the Density Formula lead to the first tight lower bound examples.
Cite as

Michael Kaufmann, Boris Klemz, Kristin Knorr, Meghana M. Reddy, Felix Schröder, and Torsten Ueckerdt. The Density Formula: One Lemma to Bound Them All. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kaufmann_et_al:LIPIcs.GD.2024.7,
  author =	{Kaufmann, Michael and Klemz, Boris and Knorr, Kristin and M. Reddy, Meghana and Schr\"{o}der, Felix and Ueckerdt, Torsten},
  title =	{{The Density Formula: One Lemma to Bound Them All}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-212913},
  doi =		{10.4230/LIPIcs.GD.2024.7},
  annote =	{Keywords: beyond-planar, density, fan-planar, fan-crossing, right-angle crossing, quasiplanar}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2024.99
Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number

Authors: Boris Klemz and Marie Diana Sieper

Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)

Abstract
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity, each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Constrained Level Planarity is known to be a remarkably difficult problem: previous results by Klemz and Rote [ACM Trans. Alg.'19] and by Brückner and Rutter [SODA'17] imply that it remains NP-hard even when restricted to graphs whose tree-depth and feedback vertex set number are bounded by a constant and even when the instances are additionally required to be either proper, meaning that each edge spans two consecutive levels, or ordered, meaning that all given partial orders are total orders. In particular, these results rule out the existence of FPT-time (even XP-time) algorithms with respect to these and related graph parameters (unless P=NP). However, the parameterized complexity of Constrained Level Planarity with respect to the vertex cover number of the input graph remained open. In this paper, we show that Constrained Level Planarity can be solved in FPT-time when parameterized by the vertex cover number. In view of the previous intractability statements, our result is best-possible in several regards: a speed-up to polynomial time or a generalization to the aforementioned smaller graph parameters is not possible, even if restricting to proper or ordered instances.
Cite as

Boris Klemz and Marie Diana Sieper. Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 99:1-99:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{klemz_et_al:LIPIcs.ICALP.2024.99,
  author =	{Klemz, Boris and Sieper, Marie Diana},
  title =	{{Constrained Level Planarity Is FPT with Respect to the Vertex Cover Number}},
  booktitle =	{51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)},
  pages =	{99:1--99:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-322-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{297},
  editor =	{Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.99},
  URN =		{urn:nbn:de:0030-drops-202428},
  doi =		{10.4230/LIPIcs.ICALP.2024.99},
  annote =	{Keywords: Parameterized Complexity, Graph Drawing, Planar Poset Diagram, Level Planarity, Constrained Level Planarity, Vertex Cover, FPT, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.20
Constrained and Ordered Level Planarity Parameterized by the Number of Levels

Authors: Václav Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink

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

Abstract
The problem Level Planarity asks for a crossing-free drawing of a graph in the plane such that vertices are placed at prescribed y-coordinates (called levels) and such that every edge is realized as a y-monotone curve. In the variant Constrained Level Planarity (CLP), each level y is equipped with a partial order ≺_y on its vertices and in the desired drawing the left-to-right order of vertices on level y has to be a linear extension of ≺_y. Ordered Level Planarity (OLP) corresponds to the special case of CLP where the given partial orders ≺_y are total orders. Previous results by Brückner and Rutter [SODA 2017] and Klemz and Rote [ACM Trans. Alg. 2019] state that both CLP and OLP are NP-hard even in severely restricted cases. In particular, they remain NP-hard even when restricted to instances whose width (the maximum number of vertices that may share a common level) is at most two. In this paper, we focus on the other dimension: we study the parameterized complexity of CLP and OLP with respect to the height (the number of levels). We show that OLP parameterized by the height is complete with respect to the complexity class XNLP, which was first studied by Elberfeld, Stockhusen, and Tantau [Algorithmica 2015] (under a different name) and recently made more prominent by Bodlaender, Groenland, Nederlof, and Swennenhuis [FOCS 2021]. It contains all parameterized problems that can be solved nondeterministically in time f(k)⋅ n^O(1) and space f(k)⋅ log n (where f is a computable function, n is the input size, and k is the parameter). If a problem is XNLP-complete, it lies in XP, but is W[t]-hard for every t. In contrast to the fact that OLP parameterized by the height lies in XP, it turns out that CLP is NP-hard even when restricted to instances of height 4. We complement this result by showing that CLP can be solved in polynomial time for instances of height at most 3.
Cite as

Václav Blažej, Boris Klemz, Felix Klesen, Marie Diana Sieper, Alexander Wolff, and Johannes Zink. Constrained and Ordered Level Planarity Parameterized by the Number of Levels. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 20:1-20:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{blazej_et_al:LIPIcs.SoCG.2024.20,
  author =	{Bla\v{z}ej, V\'{a}clav and Klemz, Boris and Klesen, Felix and Sieper, Marie Diana and Wolff, Alexander and Zink, Johannes},
  title =	{{Constrained and Ordered Level Planarity Parameterized by the Number of Levels}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{20:1--20: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.20},
  URN =		{urn:nbn:de:0030-drops-199652},
  doi =		{10.4230/LIPIcs.SoCG.2024.20},
  annote =	{Keywords: Parameterized Complexity, Graph Drawing, XNLP, XP, W\lbrackt\rbrack-hard, Level Planarity, Planar Poset Diagram, Computational Geometry}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.57
Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing

Authors: Boris Klemz

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
A hierarchical plane st-graph H can be thought of as a combinatorial description of a planar drawing Γ of a 2-connected graph G in which each edge is a y-monotone curve and each face encloses a y-monotone region (that is, a region whose intersection with any horizontal line is a line segment, a point, or empty). A drawing Γ' of H is a drawing of G such that each horizontal line intersects the same left-to-right order of edges and vertices in Γ and Γ', that is, the underlying hierarchical plane st-graph of both drawings is H. A straight-line planar drawing of a graph is convex if the boundary of each face is realized as a convex polygon. We study the computation of convex drawings of hierarchical plane st-graphs such that the outer face is realized as a prescribed polygon. Chrobak, Goodrich, and Tamassia [SoCG'96] and, independently, Kleist et al. [CGTA'19] described an idea to solve this problem in O(n^{1.1865}) time, where n is the number of vertices of the graph. Also independently, Hong and Nagamochi [J. Discrete Algorithms'10] described a completely different approach, which can be executed in O(n²) time. In this paper, we present an optimal O(n) time algorithm to solve the above problem, thereby improving the previous results by Chrobak, Goodrich, and Tamassia, Kleist et al., and by Hong and Nagamochi. Our result has applications in graph morphing. A planar morph is a continuous deformation of a graph drawing that preserves straight-line planarity. We show that our algorithm can be used as a drop-in replacement to speed up a procedure by Alamdari et al. [SICOMP'17] to morph between any two given straight-line planar drawings of the same plane graph. The running time improves from O(n^{2.1865}) to O(n²log n). To obtain our results, we devise a new strategy for computing so-called archfree paths in hierarchical plane st-graphs, which might be of independent interest.
Cite as

Boris Klemz. Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{klemz:LIPIcs.ESA.2021.57,
  author =	{Klemz, Boris},
  title =	{{Convex Drawings of Hierarchical Graphs in Linear Time, with Applications to Planar Graph Morphing}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{57:1--57:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus 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.2021.57},
  URN =		{urn:nbn:de:0030-drops-146381},
  doi =		{10.4230/LIPIcs.ESA.2021.57},
  annote =	{Keywords: convex drawing, hierarchical graph, graph drawing, computational geometry, planarity, planar graph, morphing, convexity}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.11
Adjacency Graphs of Polyhedral Surfaces

Authors: Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract
We study whether a given graph can be realized as an adjacency graph of the polygonal cells of a polyhedral surface in ℝ³. We show that every graph is realizable as a polyhedral surface with arbitrary polygonal cells, and that this is not true if we require the cells to be convex. In particular, if the given graph contains K_5, K_{5,81}, or any nonplanar 3-tree as a subgraph, no such realization exists. On the other hand, all planar graphs, K_{4,4}, and K_{3,5} can be realized with convex cells. The same holds for any subdivision of any graph where each edge is subdivided at least once, and, by a result from McMullen et al. (1983), for any hypercube. Our results have implications on the maximum density of graphs describing polyhedral surfaces with convex cells: The realizability of hypercubes shows that the maximum number of edges over all realizable n-vertex graphs is in Ω(n log n). From the non-realizability of K_{5,81}, we obtain that any realizable n-vertex graph has 𝒪(n^{9/5}) edges. As such, these graphs can be considerably denser than planar graphs, but not arbitrarily dense.
Cite as

Elena Arseneva, Linda Kleist, Boris Klemz, Maarten Löffler, André Schulz, Birgit Vogtenhuber, and Alexander Wolff. Adjacency Graphs of Polyhedral Surfaces. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 11:1-11:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{arseneva_et_al:LIPIcs.SoCG.2021.11,
  author =	{Arseneva, Elena and Kleist, Linda and Klemz, Boris and L\"{o}ffler, Maarten and Schulz, Andr\'{e} and Vogtenhuber, Birgit and Wolff, Alexander},
  title =	{{Adjacency Graphs of Polyhedral Surfaces}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{11:1--11:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.11},
  URN =		{urn:nbn:de:0030-drops-138107},
  doi =		{10.4230/LIPIcs.SoCG.2021.11},
  annote =	{Keywords: polyhedral complexes, realizability, contact representation}
}
Document
DOI: 10.4230/LIPIcs.ESA.2019.58
Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian

Authors: Michael Hoffmann and Boris Klemz

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

Abstract
We show that every triconnected planar graph of maximum degree five is subhamiltonian planar. A graph is subhamiltonian planar if it is a subgraph of a Hamiltonian planar graph or, equivalently, if it admits a 2-page book embedding. In fact, our result is stronger because we only require vertices of a separating triangle to have degree at most five, all other vertices may have arbitrary degree. This degree bound is tight: We describe a family of triconnected planar graphs that are not subhamiltonian planar and where every vertex of a separating triangle has degree at most six. Our results improve earlier work by Heath and by Bauernöppel and, independently, Bekos, Gronemann, and Raftopoulou, who showed that planar graphs of maximum degree three and four, respectively, are subhamiltonian planar. The proof is constructive and yields a quadratic time algorithm to obtain a subhamiltonian plane cycle for a given graph. As one of our main tools, which might be of independent interest, we devise an algorithm that, in a given 3-connected plane graph satisfying the above degree bounds, collapses each maximal separating triangle into a single edge such that the resulting graph is biconnected, contains no separating triangle, and no separation pair whose vertices are adjacent.
Cite as

Michael Hoffmann and Boris Klemz. Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 58:1-58:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{hoffmann_et_al:LIPIcs.ESA.2019.58,
  author =	{Hoffmann, Michael and Klemz, Boris},
  title =	{{Triconnected Planar Graphs of Maximum Degree Five are Subhamiltonian}},
  booktitle =	{27th Annual European Symposium on Algorithms (ESA 2019)},
  pages =	{58:1--58:14},
  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.58},
  URN =		{urn:nbn:de:0030-drops-111797},
  doi =		{10.4230/LIPIcs.ESA.2019.58},
  annote =	{Keywords: Graph drawing, book embedding, Hamiltonian graph, planar graph, bounded degree graph, graph augmentation, computational geometry, SPQR decomposition}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2016.37
Strongly Monotone Drawings of Planar Graphs

Authors: Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract
A straight-line drawing of a graph is a monotone drawing if for each pair of vertices there is a path which is monotonically increasing in some direction, and it is called a strongly monotone drawing if the direction of monotonicity is given by the direction of the line segment connecting the two vertices. We present algorithms to compute crossing-free strongly monotone drawings for some classes of planar graphs; namely, 3-connected planar graphs, outerplanar graphs, and 2-trees. The drawings of 3-connected planar graphs are based on primal-dual circle packings. Our drawings of outerplanar graphs depend on a new algorithm that constructs strongly monotone drawings of trees which are also convex. For irreducible trees, these drawings are strictly convex.
Cite as

Stefan Felsner, Alexander Igamberdiev, Philipp Kindermann, Boris Klemz, Tamara Mchedlidze, and Manfred Scheucher. Strongly Monotone Drawings of Planar Graphs. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{felsner_et_al:LIPIcs.SoCG.2016.37,
  author =	{Felsner, Stefan and Igamberdiev, Alexander and Kindermann, Philipp and Klemz, Boris and Mchedlidze, Tamara and Scheucher, Manfred},
  title =	{{Strongly Monotone Drawings of Planar Graphs}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.37},
  URN =		{urn:nbn:de:0030-drops-59292},
  doi =		{10.4230/LIPIcs.SoCG.2016.37},
  annote =	{Keywords: graph drawing, planar graphs, strongly monotone, strictly convex, primal-dual circle packing}
}
  • Refine by Type
  • 12 Document/PDF
  • 5 Document/HTML

  • Refine by Publication Year
  • 5 2025
  • 3 2024
  • 2 2021
  • 1 2019
  • 1 2016

  • Refine by Author
  • 7 Klemz, Boris
  • 3 Vogtenhuber, Birgit
  • 3 Wolff, Alexander
  • 2 Sieper, Marie Diana
  • 2 Ueckerdt, Torsten
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 6 Mathematics of computing → Graphs and surfaces
  • 6 Theory of computation → Computational geometry
  • 4 Human-centered computing → Graph drawings
  • 3 Mathematics of computing → Graph theory
  • 3 Mathematics of computing → Paths and connectivity problems
  • Show More...

  • Refine by Keyword
  • 2 Computational Geometry
  • 2 FPT
  • 2 Graph Drawing
  • 2 Level Planarity
  • 2 Parameterized Complexity
  • 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