DROPS

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

Document

DOI: 10.4230/LIPIcs.GD.2024.23

Intersection Graphs with and Without Product Structure

Authors: Laura Merker, Lena Scherzer, Samuel Schneider, and Torsten Ueckerdt

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

Abstract

A graph class 𝒢 admits product structure if there exists a constant k such that every G ∈ 𝒢 is a subgraph of H ⊠ P for a path P and some graph H of treewidth k. Famously, the class of planar graphs, as well as many beyond-planar graph classes are known to admit product structure. However, we have only few tools to prove the absence of product structure, and hence know of only a few interesting examples of classes. Motivated by the transition between product structure and no product structure, we investigate subclasses of intersection graphs in the plane (e.g., disk intersection graphs) and present necessary and sufficient conditions for these to admit product structure. Specifically, for a set S ⊂ ℝ² (e.g., a disk) and a real number α ∈ [0,1], we consider intersection graphs of α-free homothetic copies of S. That is, each vertex v is a homothetic copy of S of which at least an α-portion is not covered by other vertices, and there is an edge between u and v if and only if u ∩ v ≠ ∅. For α = 1 we have contact graphs, which are in most cases planar, and hence admit product structure. For α = 0 we have (among others) all complete graphs, and hence no product structure. In general, there is a threshold value α^*(S) ∈ [0,1] such that α-free homothetic copies of S admit product structure for all α > α^*(S) and do not admit product structure for all α < α^*(S). We show for a large family of sets S, including all triangles and all trapezoids, that it holds α^*(S) = 1, i.e., we have no product structure, except for the contact graphs (when α = 1). For other sets S, including regular n-gons for infinitely many values of n, we show that 0 < α^*(S) < 1 by proving upper and lower bounds.

Cite as

Laura Merker, Lena Scherzer, Samuel Schneider, and Torsten Ueckerdt. Intersection Graphs with and Without Product Structure. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 23:1-23:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{merker_et_al:LIPIcs.GD.2024.23,
  author =	{Merker, Laura and Scherzer, Lena and Schneider, Samuel and Ueckerdt, Torsten},
  title =	{{Intersection Graphs with and Without Product Structure}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{23:1--23:19},
  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.23},
  URN =		{urn:nbn:de:0030-drops-213070},
  doi =		{10.4230/LIPIcs.GD.2024.23},
  annote =	{Keywords: Product structure, intersection graphs, linear local treewidth}
}

Search Results

Documents authored by Merker, Laura

Forbidden Patterns in Mixed Linear Layouts

Abstract

Cite as

Intersection Graphs with and Without Product Structure

Abstract

Cite as

Thanks for your feedback!

Could not send message