Search Results

Documents authored by Klemz, Boris

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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact