DROPS

Document

DOI: 10.4230/LIPIcs.SWAT.2026.6

How Many Slopes Does Polynomial Area Cost?

Authors: Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

In this work, we study the interplay between the number of slopes, the number of bends per edge, and the area requirements for planar drawings of bounded-degree graphs. Our motivation stems from the fact that, while numerous algorithms produce planar drawings with few slopes for graphs of relatively small degree in polynomial area, existing approaches for higher-degree graphs often require super-polynomial area. We address this gap in the literature by presenting new constructions that yield polynomial-area drawings with few bends per edge while slightly increasing the required number of slopes, thereby providing the first systematic study of slopes, bends and area trade-offs.

Cite as

Michael A. Bekos, Eleni Katsanou, Philipp Kindermann, and Maria Eleni Pavlidi. How Many Slopes Does Polynomial Area Cost?. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.SWAT.2026.6,
  author =	{Bekos, Michael A. and Katsanou, Eleni and Kindermann, Philipp and Pavlidi, Maria Eleni},
  title =	{{How Many Slopes Does Polynomial Area Cost?}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.6},
  URN =		{urn:nbn:de:0030-drops-260424},
  doi =		{10.4230/LIPIcs.SWAT.2026.6},
  annote =	{Keywords: k-bend planar drawings, planar slope number, area requirements}
}

Document

DOI: 10.4230/LIPIcs.SWAT.2026.29

Bichromatic Classifications of Points Using Strips

Authors: Jaegun Lee, Chaeyoon Chung, and Hee-Kap Ahn

Published in: LIPIcs, Volume 370, 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)

Abstract

Given a set of n points in the plane, each colored either blue or red, we study the problem of finding a strip that separates the blue points from the red points. Specifically, we consider the following two variants: (1) locating a strip that contains no red points while maximizing the number of blue points within the strip, and (2) locating a strip that contains all blue points while minimizing the number of red points within the strip. For variant (1), we present an O(n²)-time algorithm, improving upon the previously best O(n²log n)-time result. We also show that this running time is optimal under the standard 3SUM conjecture. We also give an output-sensitive algorithm with running time O(k_{opt} n log n) that returns a strip, where k_{opt} is the number of blue points not contained within the strip in an optimal solution. We extend our results to the case of up to t parallel strips, obtaining an O(n²log n)-time algorithm. For variant (2), an optimal Θ(nlog n)-time algorithm is known for t = 1. We show 3SUM-hardness for t = 2 and give an O(n²)-time algorithm. For any t ≥ 3, we present an O(n²log n)-time algorithm.

Cite as

Jaegun Lee, Chaeyoon Chung, and Hee-Kap Ahn. Bichromatic Classifications of Points Using Strips. In 20th Scandinavian Symposium on Algorithm Theory (SWAT 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 370, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lee_et_al:LIPIcs.SWAT.2026.29,
  author =	{Lee, Jaegun and Chung, Chaeyoon and Ahn, Hee-Kap},
  title =	{{Bichromatic Classifications of Points Using Strips}},
  booktitle =	{20th Scandinavian Symposium on Algorithm Theory (SWAT 2026)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-421-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{370},
  editor =	{Fraigniaud, Pierre},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2026.29},
  URN =		{urn:nbn:de:0030-drops-260659},
  doi =		{10.4230/LIPIcs.SWAT.2026.29},
  annote =	{Keywords: Bichromatic Classification, Separation, Strip, Duality}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.15

Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity

Authors: Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong

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

Abstract

A Euclidean noncrossing Steiner (1+ε)-spanner for a point set P ⊂ ℝ² is a planar straight-line graph that, for any two points a, b ∈ P, contains a path whose length is at most 1+ε times the Euclidean distance between a and b. We construct a Euclidean noncrossing Steiner (1+ε)-spanner with O(n/ε^{3/2}) edges for any set of n points in the plane. This result improves upon the previous best upper bound of O(n/ε⁴) obtained nearly three decades ago. We also establish an almost matching lower bound: There exist n points in the plane for which any Euclidean noncrossing Steiner (1+ε)-spanner has Ω_μ(n/ε^{3/2-μ}) edges for any μ > 0. Our lower bound uses recent generalizations of the Szemerédi-Trotter theorem to disk-tube incidences in geometric measure theory.

Cite as

Sujoy Bhore, Sándor Kisfaludi‑Bak, Lazar Milenković, Csaba D. Tóth, Karol Węgrzycki, and Sampson Wong. Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{bhore_et_al:LIPIcs.SoCG.2026.15,
  author =	{Bhore, Sujoy and Kisfaludi‑Bak, S\'{a}ndor and Milenkovi\'{c}, Lazar and T\'{o}th, Csaba D. and W\k{e}grzycki, Karol and Wong, Sampson},
  title =	{{Euclidean Noncrossing Steiner Spanners of Nearly Optimal Sparsity}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.15},
  URN =		{urn:nbn:de:0030-drops-258210},
  doi =		{10.4230/LIPIcs.SoCG.2026.15},
  annote =	{Keywords: geometric network design, spanners, crossing number, incidences}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.26

Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice

Authors: Guangya Cai

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

Abstract

We study the problem of finding a fair linear scoring function over (numerical) attributes for top-k selection, ensuring fairness through a proportional representation constraint on the protected group. Existing algorithms do not scale efficiently, particularly in higher dimensions. Our hardness analysis shows that in more than two dimensions, no algorithm is likely to scale efficiently with respect to dataset size, and the computational complexity is likely to grow rapidly with dimensionality. However, the hardness results also provide key insights guiding algorithm design, leading to our two-pronged solution: (1) For small k, our analysis reveals a gap in the hardness barrier. By addressing various engineering challenges, including achieving efficient parallelism, we turn this potential of efficiency into an optimized geometry-based algorithm delivering substantial performance gains. (2) For large k, where the hardness is robust, we employ a practically efficient optimization-based algorithm which, despite being theoretically worse, achieves superior real-world performance. Experimental evaluations on real-world datasets then explore scenarios where worst-case behavior does not manifest, identifying areas critical to practical performance. Our solution achieves speedups of up to several orders of magnitude compared to the state of the art, an efficiency made possible through a tight integration of hardness analysis, algorithm design, practical engineering, and empirical evaluation.

Cite as

Guangya Cai. Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{cai:LIPIcs.SoCG.2026.26,
  author =	{Cai, Guangya},
  title =	{{Finding a Fair Scoring Function for Top-k Selection: From Hardness to Practice}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{26:1--26:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.26},
  URN =		{urn:nbn:de:0030-drops-258320},
  doi =		{10.4230/LIPIcs.SoCG.2026.26},
  annote =	{Keywords: Fairness, Top-k, Integration}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2026.63

Unavoidable Patterns and Plane Paths in Dense Topological Graphs

Authors: Balázs Keszegh, Andrew Suk, Gábor Tardos, and Ji Zeng

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

Abstract

Let C_{s,t} be the complete bipartite geometric graph, with s and t vertices on two distinct parallel lines respectively, and all s t straight-line edges drawn between them. In this paper, we show that every complete bipartite simple topological graph, with parts of size 2(k-1)⁴ + 1 and 2^{k^{5k}}, contains a topological subgraph weakly isomorphic to C_{k,k}. As a corollary, every n-vertex simple topological graph not containing a plane path of length k has at most O_k(n^{2 - 8/k⁴}) edges. When k = 3, we obtain a stronger bound by showing that every n-vertex simple topological graph not containing a plane path of length 3 has at most O(n^{4/3}) edges. We also prove that x-monotone simple topological graphs not containing a plane path of length 3 have at most a linear number of edges.

Cite as

Balázs Keszegh, Andrew Suk, Gábor Tardos, and Ji Zeng. Unavoidable Patterns and Plane Paths in Dense Topological Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 63:1-63:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{keszegh_et_al:LIPIcs.SoCG.2026.63,
  author =	{Keszegh, Bal\'{a}zs and Suk, Andrew and Tardos, G\'{a}bor and Zeng, Ji},
  title =	{{Unavoidable Patterns and Plane Paths in Dense Topological Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{63:1--63:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.63},
  URN =		{urn:nbn:de:0030-drops-258706},
  doi =		{10.4230/LIPIcs.SoCG.2026.63},
  annote =	{Keywords: graph drawing, topological graph, bipartite geometric graph, forbidden subgraph, extremal graph, thrackle}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.23

The Price of Connectivity Augmentation on Planar Graphs

Authors: Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt

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

Abstract

Given two classes of graphs, 𝒢₁ ⊆ 𝒢₂, and a c-connected graph G ∈ 𝒢₁, we wish to augment G with a smallest cardinality set of new edges F to obtain a k-connected graph G' = (V,E∪ F) ∈ 𝒢₂. In general, this is the c → k connectivity augmentation problem. Previous research considered variants where 𝒢₁ = 𝒢₂ is the class of planar graphs, plane graphs, or planar straight-line graphs. In all three settings, we prove that the c → k augmentation problem is NP-complete when 2 ≤ c < k ≤ 5. However, the connectivity of the augmented graph G' is at most 5 if 𝒢₂ is limited to planar graphs. We initiate the study of the c → k connectivity augmentation problem for arbitrary k ∈ ℕ, where 𝒢₁ is the class of planar graphs, plane graphs, or planar straight-line graphs, and 𝒢₂ is a beyond-planar class of graphs: 𝓁-planar, 𝓁-plane topological, or 𝓁-plane geometric graphs. We obtain tight bounds on the tradeoffs between the desired connectivity k and the local crossing number 𝓁 of the augmented graph G'. We also show that our hardness results apply to this setting. The connectivity augmentation problem for triangulations is intimately related to edge flips; and the minimum augmentation problem to the flip distance between triangulations. We prove that it is NP-complete to find the minimum flip distance between a given triangulation and a 4-connected triangulation, settling an open problem posed in 2014, and present an EPTAS for this problem.

Cite as

Hugo A. Akitaya, Justin Dallant, Erik D. Demaine, Michael Kaufmann, Linda Kleist, Frederick Stock, Csaba D. Tóth, and Torsten Ueckerdt. The Price of Connectivity Augmentation on Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 23:1-23:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{a.akitaya_et_al:LIPIcs.GD.2025.23,
  author =	{A. Akitaya, Hugo and Dallant, Justin and Demaine, Erik D. and Kaufmann, Michael and Kleist, Linda and Stock, Frederick and T\'{o}th, Csaba D. and Ueckerdt, Torsten},
  title =	{{The Price of Connectivity Augmentation on Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{23:1--23:24},
  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.23},
  URN =		{urn:nbn:de:0030-drops-250095},
  doi =		{10.4230/LIPIcs.GD.2025.23},
  annote =	{Keywords: connectivity augmentation, local crossing number, flip distance}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.25

Characterizing and Recognizing Twistedness

Authors: Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger

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

Abstract

In a simple drawing of a graph, any two edges intersect in at most one point (either a common endpoint or a proper crossing). A simple drawing is generalized twisted if it fulfills certain rather specific constraints on how the edges are drawn. An abstract rotation system of a graph assigns to each vertex a cyclic order of its incident edges. A realizable rotation system is one that admits a simple drawing such that at each vertex, the edges emanate in that cyclic order, and a generalized twisted rotation system can be realized as a generalized twisted drawing. Generalized twisted drawings have initially been introduced to obtain improved bounds on the size of plane substructures in any simple drawing of K_n. They have since gained independent interest due to their surprising properties. However, the definition of generalized twisted drawings is very geometric and drawing-specific. In this paper, we develop characterizations of generalized twisted drawings that enable a purely combinatorial view on these drawings and lead to efficient recognition algorithms. Concretely, we show that for any n ≥ 7, an abstract rotation system of K_n is generalized twisted if and only if all subrotation systems induced by five vertices are generalized twisted. This implies a drawing-independent and concise characterization of generalized twistedness. Besides, the result yields a simple O(n⁵)-time algorithm to decide whether an abstract rotation system is generalized twisted and sheds new light on the structural features of simple drawings. We further develop a characterization via the rotations of a pair of vertices in a drawing, which we then use to derive an O(n²)-time algorithm to decide whether a realizable rotation system is generalized twisted.

Cite as

Oswin Aichholzer, Alfredo García, Javier Tejel, Birgit Vogtenhuber, and Alexandra Weinberger. Characterizing and Recognizing Twistedness. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{aichholzer_et_al:LIPIcs.GD.2025.25,
  author =	{Aichholzer, Oswin and Garc{\'\i}a, Alfredo and Tejel, Javier and Vogtenhuber, Birgit and Weinberger, Alexandra},
  title =	{{Characterizing and Recognizing Twistedness}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{25:1--25: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.25},
  URN =		{urn:nbn:de:0030-drops-250116},
  doi =		{10.4230/LIPIcs.GD.2025.25},
  annote =	{Keywords: generalized twisted drawings, simple drawings, rotation systems, recognition, combinatorial characterization, efficient algorithms}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.26

1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs

Authors: Eliška Červenková and Jan Kratochvíl

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

Abstract

Matchstick graphs are graphs that allow plane embedding with straight edges of equal length. One-planar unit distance graphs are graphs that allow a drawing in the plane in which all edges are straight-line segments of equal length and every edge crosses at most one other edge. The maximum number of edges of a matchstick graph (1-planar unit distance graph) of order n is denoted by u₀(n) (u₁(n), respectively). It is known that u₀(n) = ⌊ 3n-√{12n-3}⌋ holds for every n. At GD'24, Gehér and Tóth proved a slightly weaker upper bound on u₁(n), but noted that no 1-planar unit distance graph G with more than u₀(|V(G)|) vertices was known. They asked if u₁(n) = u₀(n) holds for every n. We give a negative answer to this question in a much stronger way. We show that u₁(n) > u₀(n) for every n ≥ 16135. Furthermore, we show that the gap between u₁(n) and u₀(n) can be arbitrarily large by proving that for n large enough with respect to a constant α < ∜{1/3}, u₁(n)-u₀(n) ≥ α∜{n}.

Cite as

Eliška Červenková and Jan Kratochvíl. 1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 26:1-26:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cervenkova_et_al:LIPIcs.GD.2025.26,
  author =	{\v{C}ervenkov\'{a}, Eli\v{s}ka and Kratochv{\'\i}l, Jan},
  title =	{{1-Planar Unit Distance Graphs with More Edges Than Matchstick Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{26:1--26:10},
  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.26},
  URN =		{urn:nbn:de:0030-drops-250126},
  doi =		{10.4230/LIPIcs.GD.2025.26},
  annote =	{Keywords: planar graph, unit distance graph, matchstick graph, 1-planar graph}
}

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2025.49

Defective Linear Layouts of Graphs (Poster Abstract)

Authors: Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger

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

Abstract

A linear layout of a graph defines a total order of the vertices and partitions the edges into either stacks or queues, i.e., crossing-free and non-nested sets of edges along the order, respectively. In this work, we study defective linear layouts that allow forbidden patterns among edges of the same set. Our focus is on k-defective stack layouts and k-defective queue layouts, in which the conflict graph representing the forbidden patterns among the edges of each stack or queue has maximum degree at most k.

Cite as

Michael A. Bekos, Carla Binucci, Emilio Di Giacomo, Walter Didimo, Luca Grilli, Maria Eleni Pavlidi, Alessandra Tappini, and Alexandra Weinberger. Defective Linear Layouts of Graphs (Poster Abstract). In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 49:1-49:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.49,
  author =	{Bekos, Michael A. and Binucci, Carla and Di Giacomo, Emilio and Didimo, Walter and Grilli, Luca and Pavlidi, Maria Eleni and Tappini, Alessandra and Weinberger, Alexandra},
  title =	{{Defective Linear Layouts of Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{49:1--49:4},
  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.49},
  URN =		{urn:nbn:de:0030-drops-250350},
  doi =		{10.4230/LIPIcs.GD.2025.49},
  annote =	{Keywords: Linear layouts, stack layouts, queue layouts, defective layouts}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.16

Structural Parameterizations of k-Planarity

Authors: Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada

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

Abstract

The concept of k-planarity is extensively studied in the context of Beyond Planarity. A graph is k-planar if it admits a drawing in the plane in which each edge is crossed at most k times. The local crossing number of a graph is the minimum integer k such that it is k-planar. The problem of determining whether an input graph is 1-planar is known to be NP-complete even for near-planar graphs [Cabello and Mohar, SIAM J. Comput. 2013], that is, the graphs obtained from planar graphs by adding a single edge. Moreover, the local crossing number is hard to approximate within a factor 2 - ε for any ε > 0 [Urschel and Wellens, IPL 2021]. To address this computational intractability, Bannister, Cabello, and Eppstein [JGAA 2018] investigated the parameterized complexity of the case of k = 1, particularly focusing on structural parameterizations on input graphs, such as treedepth, vertex cover number, and feedback edge number. In this paper, we extend their approach by considering the general case k ≥ 1 and give (tight) parameterized upper and lower bound results. In particular, we strengthen the aforementioned lower bound results to subclasses of constant-treewidth graphs: we show that testing 1-planarity is NP-complete even for near-planar graphs with feedback vertex set number at most 3 and pathwidth at most 4, and the local crossing number is hard to approximate within any constant factor for graphs with feedback vertex set number at most 2.

Cite as

Tatsuya Gima, Yasuaki Kobayashi, and Yuto Okada. Structural Parameterizations of k-Planarity. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gima_et_al:LIPIcs.GD.2025.16,
  author =	{Gima, Tatsuya and Kobayashi, Yasuaki and Okada, Yuto},
  title =	{{Structural Parameterizations of k-Planarity}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{16:1--16: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.16},
  URN =		{urn:nbn:de:0030-drops-250021},
  doi =		{10.4230/LIPIcs.GD.2025.16},
  annote =	{Keywords: 1-planar graphs, local crossing number, beyond planarity, parameterized complexity, kernelization}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.14

OOPS: Optimized One-Planarity Solver via SAT

Authors: Sergey Pupyrev

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

Abstract

We present OOPS (Optimized One-Planarity Solver), a practical heuristic for recognizing 1-planar graphs and several important subclasses. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once - a natural generalization of planar graphs that has received increasing attention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time, recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable. The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance, enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexity of the problem, our method is substantially faster in practice than naïve or brute-force algorithms. In addition to demonstrating the empirical performance of our solver on synthetic and real-world instances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically, we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families. Our implementation of the algorithm is publicly available to support further exploration in the field.

Cite as

Sergey Pupyrev. OOPS: Optimized One-Planarity Solver via SAT. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pupyrev:LIPIcs.GD.2025.14,
  author =	{Pupyrev, Sergey},
  title =	{{OOPS: Optimized One-Planarity Solver via SAT}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{14:1--14:19},
  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.14},
  URN =		{urn:nbn:de:0030-drops-250004},
  doi =		{10.4230/LIPIcs.GD.2025.14},
  annote =	{Keywords: beyond planarity, 1-planar graph, SAT, book embeddings, upward 1-planarity}
}

Document

DOI: 10.4230/LIPIcs.GD.2025.4

Heuristics for Exact 1-Planarity Testing

Authors: Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter

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

Abstract

Since many real-world graphs are nonplanar, the study of graphs that allow few crossings per edge has been an active subfield of graph theory in recent years. One of the most natural generalizations of planar graphs are the so-called 1-planar graphs that admit a drawing with at most one crossing per edge. Unfortunately, testing whether a graph is 1-planar is known to be NP-complete even for very restricted graph classes. On the positive side, Binucci, Didimo and Montecchiani [Binucci et al., 2023] presented the first practical algorithm for testing 1-planarity based on an easy-to-implement backtracking strategy. We build on this idea and systematically explore the design choices of such algorithms and propose several new ingredients, such as different branching strategies and multiple filter criteria that allow us to reject certain branches in the search tree early on. We conduct an extensive experimental evaluation that evaluates the efficiency and effectiveness of these ingredients. Given a time limit of three hours per instance, our best configuration is able to solve more than 95% of the non-planar instances from the well-known North and Rome graphs with up to 50 vertices. Notably, the median running time for solved instances is well below 4 seconds.

Cite as

Simon D. Fink, Miriam Münch, Matthias Pfretzschner, and Ignaz Rutter. Heuristics for Exact 1-Planarity Testing. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 4:1-4:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fink_et_al:LIPIcs.GD.2025.4,
  author =	{Fink, Simon D. and M\"{u}nch, Miriam and Pfretzschner, Matthias and Rutter, Ignaz},
  title =	{{Heuristics for Exact 1-Planarity Testing}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{4:1--4:19},
  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.4},
  URN =		{urn:nbn:de:0030-drops-249909},
  doi =		{10.4230/LIPIcs.GD.2025.4},
  annote =	{Keywords: 1-Planarity, Experiments, Backtracking}
}

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

DOI: 10.4230/LIPIcs.GD.2025.31

From Local Pair-Crossing Number to Local Crossing Number

Authors: Jacob Fox, János Pach, and Andrew Suk

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

Abstract

We prove that if a graph can be drawn in the plane such that each edge crosses at most k other edges, then it can be redrawn so that each edge participates in at most k³+O(k²) crossings. This improves the previous exponential bound that follows from a result of Schaefer and Štefankovič and answers a question of Ackerman and Schaefer.

Cite as

Jacob Fox, János Pach, and Andrew Suk. From Local Pair-Crossing Number to Local Crossing Number. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 31:1-31:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{fox_et_al:LIPIcs.GD.2025.31,
  author =	{Fox, Jacob and Pach, J\'{a}nos and Suk, Andrew},
  title =	{{From Local Pair-Crossing Number to Local Crossing Number}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{31:1--31:6},
  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.31},
  URN =		{urn:nbn:de:0030-drops-250170},
  doi =		{10.4230/LIPIcs.GD.2025.31},
  annote =	{Keywords: Crossing numbers, pair crossing numbers}
}

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}
}

27 Search Results for "Tóth, Géza"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message