13 Search Results for "Norin, Sergey"

Document
DOI: 10.4230/LIPIcs.SoCG.2026.18
Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

Authors: Thomas Bläsius, Emil Dohse, Deborah Haun, and Laura Merker

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

Abstract
Hyperbolic uniform disk graphs (HUDGs) are intersection graphs of disks with some radius r in the hyperbolic plane, where r may be constant or depend on the number of vertices in a family of HUDGs. We show that HUDGs with constant clique number do not admit product structure, i.e., that there is no constant c such that every such graph is a subgraph of H ⊠ P for some graph H of treewidth at most c. This justifies that HUDGs are described as not having a grid-like structure in the literature, and is in contrast to unit disk graphs in the Euclidean plane, whose grid-like structure is evident from the fact that they are subgraphs of the strong product of two paths and a clique of constant size [Dvořák et al., '21, MATRIX Annals]. By allowing H to be any graph of constant treewidth instead of a path-like graph, we reject the possibility of a grid-like structure not merely by the maximum degree (which is unbounded for HUDGs) but due to their global structure. We complement this by showing that for every (sub-)constant r, HUDGs admit product structure, whereas the typical hyperbolic behavior is observed if r grows with the number of vertices. Our proof involves a family of n-vertex HUDGs with radius log n that has bounded clique number but unbounded treewidth, and one for which the ratio of treewidth and clique number is log n / log log n. Up to a log log n factor, this negatively answers a question raised by Bläsius et al. [SoCG '25] asking whether balanced separators of HUDGs with radius log n can be covered by less than log n cliques. Our results also imply that the local and layered tree-independence number of HUDGs are both unbounded, answering an open question of Dallard et al. [arXiv '25].
Cite as

Thomas Bläsius, Emil Dohse, Deborah Haun, and Laura Merker. Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 18:1-18:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{blasius_et_al:LIPIcs.SoCG.2026.18,
  author =	{Bl\"{a}sius, Thomas and Dohse, Emil and Haun, Deborah and Merker, Laura},
  title =	{{Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{18:1--18: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.18},
  URN =		{urn:nbn:de:0030-drops-258249},
  doi =		{10.4230/LIPIcs.SoCG.2026.18},
  annote =	{Keywords: hyperbolic uniform disk graphs, product structure, treewidth}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.24
Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support

Authors: Reilly Browne and Hsien-Chih Chang

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

Abstract
Given an unweighted graph G, the minimum r-dominating set problem asks for a subset of vertices S of the smallest cardinality, such that every vertex in G is within radius r to some vertex in S. While the r-dominating set problem on planar graph admits PTAS from Baker’s shifting/layering technique when r is a constant, the problem becomes significantly harder when r can depend on n. In fact, under Exponential-Time Hypothesis, Fox-Epstein ηl [SODA 2019] observed that no efficient PTAS can exist for the unbounded r-dominating set problem on planar graphs. One may consider even harder weighted-variant known as the vertex-weighted metric r-dominating set, where edges are associated with lengths, and every vertex is associated with a positive-valued weight, and the goal is to compute an r-dominating set with minimum total weight. As a result, people resorted to bicriteria algorithms by allowing the returned solution to use radius-(1+ε)r balls instead, in addition to the total weight being a 1+ε approximation to the optimal value. We establish the first single-criteria polynomial-time O(1)-approximation algorithm for the vertex-weighted metric r-dominating set problem on planar graphs when r is part of the input, and can be arbitrarily large compared to n. Our new (single-criteria) O(1)-approximation algorithm uses the quasi-uniformity sampling technique of Chan et al. [SODA 2012] by bounding the shallow cell complexity of the (unbounded) radius-r ball system to be linear in n. To this end we have two technical innovations: 1) The discrete ball system on planar graphs are neither pseudodisks nor have well-defined boundaries for standard union-complexity arguments. We construct a support graph for arbitrary distance ball systems as contractions of Voronoi cells; the sparseness comes as a byproduct. 2) We present an assignment of each depth-(≥3) cell to a unique 3-tuple of ball centers. This allows us to use standard Clarkson-Shor techniques to reduce the counting to cells of depth exactly 3, which we prove to be size O(n) by a novel geometric argument based on our support being a Voronoi contraction.
Cite as

Reilly Browne and Hsien-Chih Chang. Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 24:1-24:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{browne_et_al:LIPIcs.SoCG.2026.24,
  author =	{Browne, Reilly and Chang, Hsien-Chih},
  title =	{{Single-Criteria Metric r-Dominating Set Problem via Minor-Preserving Support}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{24:1--24: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.24},
  URN =		{urn:nbn:de:0030-drops-258300},
  doi =		{10.4230/LIPIcs.SoCG.2026.24},
  annote =	{Keywords: Minimum dominating set, planar graphs, shallow cell complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2026.55
Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion

Authors: Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract
In property testing, a tester makes queries to (an oracle for) a graph and, on a graph having or being far from having a property P, it decides with high probability whether the graph satisfies P or not. Often, testers are restricted to a constant number of queries. While the graph properties for which there exists such a tester are somewhat well characterized in the dense graph model, it is not the case for sparse graphs. In this area, Czumaj and Sohler (FOCS’19) proved that H-freeness (i.e. the property of excluding the graph H as a subgraph) can be tested with constant queries on planar graphs as well as on graph classes excluding a minor. Using results from the sparsity toolkit, we propose a simpler alternative to the proof of Czumaj and Sohler, for a statement generalized to the broader notion of bounded expansion. That is, we prove that for any class 𝒞 with bounded expansion and any graph H, testing H-freeness can be done with constant query complexity on any graph G in 𝒞, where the constant depends on H and 𝒞, but is independent of G. While classes excluding a minor are prime examples of classes with bounded expansion, so are, for example, cubic graphs, graph classes with bounded maximum degree, or graphs of bounded book thickness. Additionally, random graphs with bounded average degree almost surely have bounded expansion.
Cite as

Samuel Humeau, Mamadou Moustapha Kanté, Daniel Mock, Timothé Picavet, and Alexandre Vigny. Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{humeau_et_al:LIPIcs.STACS.2026.55,
  author =	{Humeau, Samuel and Kant\'{e}, Mamadou Moustapha and Mock, Daniel and Picavet, Timoth\'{e} and Vigny, Alexandre},
  title =	{{Testing H-Freeness on Sparse Graphs, the Case of Bounded Expansion}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.55},
  URN =		{urn:nbn:de:0030-drops-255441},
  doi =		{10.4230/LIPIcs.STACS.2026.55},
  annote =	{Keywords: Property testing, Sparsity, Bounded expansion, Treedepth}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.12
Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments

Authors: Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
The Planar Separator Theorem, which states that any planar graph 𝒢 has a separator consisting of O(√n) nodes whose removal partitions 𝒢 into components of size at most 2n/3, is a widely used tool to obtain fast algorithms on planar graphs. Intersection graphs of disks, which generalize planar graphs, do not admit such separators. It has recently been shown that disk graphs do admit so-called clique-based separators that consist of O(√n) cliques. This result has been generalized to intersection graphs of various other types of disk-like objects. Unfortunately, segment intersection graphs do not admit small clique-based separators, because they can contain arbitrarily large bicliques. This is true even in the simple case of axis-aligned segments. In this paper we therefore introduce biclique-based separators (and, in particular, star-based separators), which are separators consisting of a small number of bicliques (or stars). We prove that any c-oriented set of n segments in the plane, where c is a constant, admits a star-based separator consisting of O(√n) stars. In fact, our result is more general, as it applies to any set of n pseudo-segments that is partitioned into c subsets such that the pseudo-segments in the same subset are pairwise disjoint. We extend our result to intersection graphs of c-oriented polygons. These results immediately lead to an almost-exact distance oracle for such intersection graphs, which has O(n√n) storage and O(√n) query time, and that can report the hop-distance between any two query nodes in the intersection graph with an additive error of at most 2. This is the first distance oracle for such types of intersection graphs that has subquadratic storage and sublinear query time and that only has an additive error.
Cite as

Mark de Berg, Bart M. P. Jansen, and Jeroen S. K. Lamme. Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{deberg_et_al:LIPIcs.ISAAC.2025.12,
  author =	{de Berg, Mark and Jansen, Bart M. P. and Lamme, Jeroen S. K.},
  title =	{{Star-Based Separators for Intersection Graphs of c-Colored Pseudo-Segments}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.12},
  URN =		{urn:nbn:de:0030-drops-249207},
  doi =		{10.4230/LIPIcs.ISAAC.2025.12},
  annote =	{Keywords: Computational geometry, intersection graphs, biclique-based separators, distance oracles}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.28
Treewidth of Outer k-Planar Graphs

Authors: Rafał Pyzik

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

Abstract
Treewidth is an important structural graph parameter that quantifies how closely a graph resembles a tree-like structure. It has applications in many algorithmic and combinatorial problems. In this paper, we study the treewidth of outer k-planar graphs, that is, graphs admitting a convex drawing (a straight-line drawing where all vertices lie on a circle) in which every edge crosses at most k other edges. We also consider the more general class of outer min-k-planar graphs, which are graphs admitting a convex drawing where for every crossing of two edges at least one of these edges is crossed at most k times. Firman, Gutowski, Kryven, Okada and Wolff [GD 2024] proved that every outer k-planar graph has treewidth at most 1.5k+2 and provided a lower bound of k+2 for even k. We establish a lower bound of 1.5k+0.5 for every odd k. Additionally, they showed that every outer min-k-planar graph has treewidth at most 3k+1. We improve this upper bound to 3⋅⌊k/2⌋+4. Our approach also allows us to upper bound the separation number, a parameter closely related to treewidth, of outer min-k-planar graphs by 2⋅⌊k/2⌋+4. This improves upon the previous bound of 2k+1 and achieves a bound with an optimal multiplicative constant.
Cite as

Rafał Pyzik. Treewidth of Outer k-Planar Graphs. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pyzik:LIPIcs.GD.2025.28,
  author =	{Pyzik, Rafa{\l}},
  title =	{{Treewidth of Outer k-Planar Graphs}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{28:1--28:16},
  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.28},
  URN =		{urn:nbn:de:0030-drops-250141},
  doi =		{10.4230/LIPIcs.GD.2025.28},
  annote =	{Keywords: treewidth, outer k-planar graphs, outer min-k-planar graphs, separation number}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.26
Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set

Authors: Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond

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

Abstract
The paper deals with the Feedback Vertex Set problem parameterized by the solution size. Given a graph G and a parameter k, one has to decide if there is a set S of at most k vertices such that G-S is acyclic. Assuming the Exponential Time Hypothesis, it is known that FVS cannot be solved in time 2^{o(k)}n^{𝒪(1)} in general graphs. To overcome this, many recent results considered FVS restricted to particular intersection graph classes and provided such 2^{o(k)}n^{𝒪(1)} algorithms. In this paper we provide generic conditions on a graph class for the existence of an algorithm solving FVS in subexponential FPT time, i.e. time 2^k^ε poly(n), for some ε < 1, where n denotes the number of vertices of the instance and k the parameter. On the one hand this result unifies algorithms that have been proposed over the years for several graph classes such as planar graphs, map graphs, unit-disk graphs, pseudo-disk graphs, and string graphs of bounded edge-degree. On the other hand it extends the tractability horizon of FVS to new classes that are not amenable to previously used techniques, in particular intersection graphs of "thin" objects like segment graphs or more generally s-string graphs.
Cite as

Gaétan Berthe, Marin Bougeret, Daniel Gonçalves, and Jean-Florent Raymond. Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{berthe_et_al:LIPIcs.ICALP.2025.26,
  author =	{Berthe, Ga\'{e}tan and Bougeret, Marin and Gon\c{c}alves, Daniel and Raymond, Jean-Florent},
  title =	{{Pushing the Frontiers of Subexponential FPT Time for Feedback Vertex Set}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-234036},
  doi =		{10.4230/LIPIcs.ICALP.2025.26},
  annote =	{Keywords: Subexponential FPT algorithms, geometric intersection graphs}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.129
An Upper Bound on the Weisfeiler-Leman Dimension

Authors: Thomas Schneider and Pascal Schweitzer

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

Abstract
The Weisfeiler-Leman (WL) algorithms form a family of incomplete approaches to the graph isomorphism problem. They recently found various applications in algorithmic group theory and machine learning. In fact, the algorithms form a parameterized family: for each k ∈ ℕ there is a corresponding k-dimensional algorithm WLk. The algorithms become increasingly powerful with increasing dimension, but at the same time the running time increases. The WL-dimension of a graph G is the smallest k ∈ ℕ for which WLk correctly decides isomorphism between G and every other graph. In some sense, the WL-dimension measures how difficult it is to test isomorphism of one graph to others using a fairly general class of combinatorial algorithms. Nowadays, it is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on n vertices is at most 3/20 ⋅ n + o(n) = 0.15 ⋅ n + o(n). Reducing the question to coherent configurations, the proof develops various techniques to analyze their structure. This includes sufficient conditions under which a fiber can be restored uniquely up to isomorphism if it is removed, a recursive proof exploiting a degree reduction and treewidth bounds, as well as an exhaustive analysis of interspaces involving small fibers. As a base case, we also analyze the dimension of coherent configurations with small fiber size and thereby graphs with small color class size.
Cite as

Thomas Schneider and Pascal Schweitzer. An Upper Bound on the Weisfeiler-Leman Dimension. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 129:1-129:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schneider_et_al:LIPIcs.ICALP.2025.129,
  author =	{Schneider, Thomas and Schweitzer, Pascal},
  title =	{{An Upper Bound on the Weisfeiler-Leman Dimension}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{129:1--129:18},
  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.129},
  URN =		{urn:nbn:de:0030-drops-235065},
  doi =		{10.4230/LIPIcs.ICALP.2025.129},
  annote =	{Keywords: Weisfeiler-Leman dimension, descriptive complexity, coherent configurations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.36
Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs

Authors: James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty

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

Abstract
In this paper, we consider the class 𝒞^d of sphere intersection graphs in R^d for d ≥ 2. We show that for each integer t, the class of all graphs in 𝒞^d that exclude K_{t,t} as a subgraph has strongly sublinear separators. We also prove that 𝒞^d has asymptotic dimension at most 2d+2.
Cite as

James Davies, Agelos Georgakopoulos, Meike Hatzel, and Rose McCarty. Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{davies_et_al:LIPIcs.SoCG.2025.36,
  author =	{Davies, James and Georgakopoulos, Agelos and Hatzel, Meike and McCarty, Rose},
  title =	{{Strongly Sublinear Separators and Bounded Asymptotic Dimension for Sphere Intersection Graphs}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{36:1--36: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.36},
  URN =		{urn:nbn:de:0030-drops-231881},
  doi =		{10.4230/LIPIcs.SoCG.2025.36},
  annote =	{Keywords: Intersection graphs, strongly sublinear separators, asymptotic dimension}
}
Document
DOI: 10.4230/LIPIcs.STACS.2025.56
Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs

Authors: Julia Katheder, Michael Kaufmann, Sergey Pupyrev, and Torsten Ueckerdt

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
Some of the most important open problems for linear layouts of graphs ask for the relation between a graph’s queue number and its stack number or mixed number. In such, we seek a vertex order and edge partition of G into parts with pairwise non-crossing edges (a stack) or with pairwise non-nesting edges (a queue). Allowing only stacks, only queues, or both, the minimum number of required parts is the graph’s stack number sn(G), queue number qn(G), and mixed number mn(G), respectively. Already in 1992, Heath and Rosenberg asked whether qn(G) is bounded in terms of sn(G), that is, whether stacks "can be transformed into" queues. This is equivalent to bipartite 3-stack graphs having bounded queue number (Dujmović and Wood, 2005). Recently, Alam et al. asked whether qn(G) is bounded in terms of mn(G), which we show to also be equivalent to the previous questions. We approach the problem by considering separated linear layouts of bipartite graphs. In this natural setting all vertices of one part must precede all vertices of the other part. Separated stack and queue numbers coincide, and for fixed vertex orders, graphs with bounded separated stack/queue number can be characterized and efficiently recognized, whereas the separated mixed layouts are more challenging. In this work, we thoroughly investigate the relationship between separated and non-separated, mixed and pure linear layouts.
Cite as

Julia Katheder, Michael Kaufmann, Sergey Pupyrev, and Torsten Ueckerdt. Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{katheder_et_al:LIPIcs.STACS.2025.56,
  author =	{Katheder, Julia and Kaufmann, Michael and Pupyrev, Sergey and Ueckerdt, Torsten},
  title =	{{Transforming Stacks into Queues: Mixed and Separated Layouts of Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{56:1--56:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.56},
  URN =		{urn:nbn:de:0030-drops-228819},
  doi =		{10.4230/LIPIcs.STACS.2025.56},
  annote =	{Keywords: Separated linear Layouts, Stack Number, Queue Number, mixed Number, bipartite Graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.21
Adjacency Labeling Schemes for Small Classes

Authors: Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
A graph class admits an implicit representation if, for every positive integer n, its n-vertex graphs have a O(log n)-bit (adjacency) labeling scheme, i.e., their vertices can be labeled by binary strings of length O(log n) such that the presence of an edge between any pair of vertices can be deduced solely from their labels. The famous Implicit Graph Conjecture posited that every hereditary (i.e., closed under taking induced subgraphs) factorial (i.e., containing 2^O(n log n) n-vertex graphs) class admits an implicit representation. The conjecture was recently refuted [Hatami and Hatami, FOCS '22], and does not even hold among monotone (i.e., closed under taking subgraphs) factorial classes [Bonnet et al., ICALP '24]. However, monotone small (i.e., containing at most n! cⁿ many n-vertex graphs for some constant c) classes do admit implicit representations. This motivates the Small Implicit Graph Conjecture: Every hereditary small class admits an O(log n)-bit labeling scheme. We provide evidence supporting the Small Implicit Graph Conjecture. First, we show that every small weakly sparse (i.e., excluding some fixed bipartite complete graph as a subgraph) class has an implicit representation. This is a consequence of the following fact of independent interest proved in the paper: Every weakly sparse small class has bounded expansion (hence, in particular, bounded degeneracy). Second, we show that every hereditary small class admits an O(log³ n)-bit labeling scheme, which provides a substantial improvement of the best-known polynomial upper bound of n^(1-ε) on the size of adjacency labeling schemes for such classes. This is a consequence of another fact of independent interest proved in the paper: Every small class has neighborhood complexity O(n log n).
Cite as

Édouard Bonnet, Julien Duron, John Sylvester, and Viktor Zamaraev. Adjacency Labeling Schemes for Small Classes. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 21:1-21:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bonnet_et_al:LIPIcs.ITCS.2025.21,
  author =	{Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor},
  title =	{{Adjacency Labeling Schemes for Small Classes}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.21},
  URN =		{urn:nbn:de:0030-drops-226493},
  doi =		{10.4230/LIPIcs.ITCS.2025.21},
  annote =	{Keywords: Adjacency labeling, degeneracy, weakly sparse classes, small classes, implicit graph conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.58
Testability and Local Certification of Monotone Properties in Minor-Closed Classes

Authors: Louis Esperet and Sergey Norin

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The main problem in the area of graph property testing is to understand which graph properties are testable, which means that with constantly many queries to any input graph G, a tester can decide with good probability whether G satisfies the property, or is far from satisfying the property. Testable properties are well understood in the dense model and in the bounded degree model, but little is known in sparse graph classes when graphs are allowed to have unbounded degree. This is the setting of the sparse model. We prove that for any proper minor-closed class 𝒢, any monotone property (i.e., any property that is closed under taking subgraphs) is testable for graphs from 𝒢 in the sparse model. This extends a result of Czumaj and Sohler (FOCS'19), who proved it for monotone properties with finitely many forbidden subgraphs. Our result implies for instance that for any integers k and t, k-colorability of K_t-minor free graphs is testable in the sparse model. Elek recently proved that monotone properties of bounded degree graphs from minor-closed classes that are closed under disjoint union can be verified by an approximate proof labeling scheme in constant time. We show again that the assumption of bounded degree can be omitted in his result.
Cite as

Louis Esperet and Sergey Norin. Testability and Local Certification of Monotone Properties in Minor-Closed Classes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 58:1-58:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{esperet_et_al:LIPIcs.ICALP.2022.58,
  author =	{Esperet, Louis and Norin, Sergey},
  title =	{{Testability and Local Certification of Monotone Properties in Minor-Closed Classes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{58:1--58:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.58},
  URN =		{urn:nbn:de:0030-drops-163997},
  doi =		{10.4230/LIPIcs.ICALP.2022.58},
  annote =	{Keywords: Property testing, sparse model, local certification, minor-closed classes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2020.31
Flexible List Colorings in Graphs with Special Degeneracy Conditions

Authors: Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho

Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)

Abstract
For a given ε > 0, we say that a graph G is ε-flexibly k-choosable if the following holds: for any assignment L of lists of size k on V(G), if a preferred color is requested at any set R of vertices, then at least ε |R| of these requests are satisfied by some L-coloring. We consider flexible list colorings in several graph classes with certain degeneracy conditions. We characterize the graphs of maximum degree Δ that are ε-flexibly Δ-choosable for some ε = ε(Δ) > 0, which answers a question of Dvořák, Norin, and Postle [List coloring with requests, JGT 2019]. We also show that graphs of treewidth 2 are 1/3-flexibly 3-choosable, answering a question of Choi et al. [arXiv 2020], and we give conditions for list assignments by which graphs of treewidth k are 1/(k+1)-flexibly (k+1)-choosable. We show furthermore that graphs of treedepth k are 1/k-flexibly k-choosable. Finally, we introduce a notion of flexible degeneracy, which strengthens flexible choosability, and we show that apart from a well-understood class of exceptions, 3-connected non-regular graphs of maximum degree Δ are flexibly (Δ - 1)-degenerate.
Cite as

Peter Bradshaw, Tomáš Masařík, and Ladislav Stacho. Flexible List Colorings in Graphs with Special Degeneracy Conditions. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bradshaw_et_al:LIPIcs.ISAAC.2020.31,
  author =	{Bradshaw, Peter and Masa\v{r}{\'\i}k, Tom\'{a}\v{s} and Stacho, Ladislav},
  title =	{{Flexible List Colorings in Graphs with Special Degeneracy Conditions}},
  booktitle =	{31st International Symposium on Algorithms and Computation (ISAAC 2020)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-173-3},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{181},
  editor =	{Cao, Yixin and Cheng, Siu-Wing and Li, Minming},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.31},
  URN =		{urn:nbn:de:0030-drops-133750},
  doi =		{10.4230/LIPIcs.ISAAC.2020.31},
  annote =	{Keywords: Flexibility, List Coloring, Choosability, Degeneracy}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2015.78
Large Supports are Required for Well-Supported Nash Equilibria

Authors: Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu

Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)

Abstract
We prove that for any constant k and any epsilon < 1, there exist bimatrix win-lose games for which every epsilon-WSNE requires supports of cardinality greater than k. To do this, we provide a graph-theoretic characterization of win-lose games that possess epsilon-WSNE with constant cardinality supports. We then apply a result in additive number theory of Haight to construct win-lose games that do not satisfy the requirements of the characterization. These constructions disprove graph theoretic conjectures of Daskalakis, Mehta and Papadimitriou and Myers.
Cite as

Yogesh Anbalagan, Hao Huang, Shachar Lovett, Sergey Norin, Adrian Vetta, and Hehui Wu. Large Supports are Required for Well-Supported Nash Equilibria. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 78-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{anbalagan_et_al:LIPIcs.APPROX-RANDOM.2015.78,
  author =	{Anbalagan, Yogesh and Huang, Hao and Lovett, Shachar and Norin, Sergey and Vetta, Adrian and Wu, Hehui},
  title =	{{Large Supports are Required for Well-Supported Nash Equilibria}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)},
  pages =	{78--84},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-89-7},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{40},
  editor =	{Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  URN =		{urn:nbn:de:0030-drops-52959},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2015.78},
  annote =	{Keywords: bimatrix games, well-supported Nash equilibria}
}
  • Refine by Type
  • 13 Document/PDF
  • 10 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 7 2025
  • 1 2022
  • 1 2020
  • 1 2015

  • Refine by Author
  • 2 Norin, Sergey
  • 1 Anbalagan, Yogesh
  • 1 Berthe, Gaétan
  • 1 Bläsius, Thomas
  • 1 Bonnet, Édouard
  • Show More...

  • Refine by Series/Journal
  • 13 LIPIcs

  • Refine by Classification
  • 6 Mathematics of computing → Graph theory
  • 3 Mathematics of computing → Combinatorics
  • 3 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Computational geometry
  • 2 Theory of computation → Streaming, sublinear and near linear time algorithms
  • Show More...

  • Refine by Keyword
  • 2 Property testing
  • 2 treewidth
  • 1 Adjacency labeling
  • 1 Bounded expansion
  • 1 Choosability
  • 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