DROPS

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.STACS.2025.45

Forbidden Patterns in Mixed Linear Layouts

Authors: Deborah Haun, Laura Merker, and Sergey Pupyrev

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

Abstract

An ordered graph is a graph with a total order over its vertices. A linear layout of an ordered graph is a partition of the edges into sets of either non-crossing edges, called stacks, or non-nesting edges, called queues. The stack (queue) number of an ordered graph is the minimum number of required stacks (queues). Mixed linear layouts combine these layouts by allowing each set of edges to form either a stack or a queue. The minimum number of stacks plus queues is called the mixed page number. It is well known that ordered graphs with small stack number are characterized, up to a function, by the absence of large twists (that is, pairwise crossing edges). Similarly, ordered graphs with small queue number are characterized by the absence of large rainbows (that is, pairwise nesting edges). However, no such characterization via forbidden patterns is known for mixed linear layouts. We address this gap by introducing patterns similar to twists and rainbows, which we call thick patterns; such patterns allow a characterization, again up to a function, of mixed linear layouts of bounded-degree graphs. That is, we show that a family of ordered graphs with bounded maximum degree has bounded mixed page number if and only if the size of the largest thick pattern is bounded. In addition, we investigate an exact characterization of ordered graphs whose mixed page number equals a fixed integer k via a finite set of forbidden patterns. We show that for k = 2, there is no such characterization, which supports the nature of our first result.

Cite as

Deborah Haun, Laura Merker, and Sergey Pupyrev. Forbidden Patterns in Mixed Linear Layouts. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 45:1-45:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{haun_et_al:LIPIcs.STACS.2025.45,
  author =	{Haun, Deborah and Merker, Laura and Pupyrev, Sergey},
  title =	{{Forbidden Patterns in Mixed Linear Layouts}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{45:1--45:21},
  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.45},
  URN =		{urn:nbn:de:0030-drops-228717},
  doi =		{10.4230/LIPIcs.STACS.2025.45},
  annote =	{Keywords: Ordered Graphs, linear Layout, mixed linear Layout, Stack Layout, Queue Layout}
}

Search Results

Documents authored by Haun, Deborah

Product Structure and Treewidth of Hyperbolic Uniform Disk Graphs

Abstract

Cite as

Forbidden Patterns in Mixed Linear Layouts

Abstract

Cite as

Thanks for your feedback!

Could not send message