DROPS

Document

DOI: 10.4230/LIPIcs.GD.2026.15

On 2-Layer k-Matching-Planar Graphs

Authors: Saeed Odak, Jonathan Rollin, and Torben Scheele

Published in: LIPIcs, Volume 396, 34th International Symposium on Graph Drawing and Network Visualization (GD 2026)

Abstract

A graph is k-matching-planar if it admits a drawing in the plane such that, for every edge e, the edges crossing e contain no matching of size greater than k. The class of k-matching-planar graphs generalizes other beyond-planar graph classes, such as k-planar and fan-planar graphs. In a 2-layer drawing of a bipartite graph, the vertices of the two bipartition classes are placed on two parallel horizontal lines and edges are drawn as straight-line segments between them. We prove that every graph with a 2-layer k-matching-planar drawing has pathwidth at most 2k+1. Moreover, for every k ≥ 0, we construct a graph with a 2-layer k-matching-planar drawing whose pathwidth is 3⌊k/2⌋ + 1. On the algorithmic side, we consider the one-sided recognition problem where a fixed embedding of the vertices on one side is given. We show that this problem is NP-hard. On the other hand, we prove that the problem is fixed-parameter tractable with respect to k. Finally, we prove that the two-sided variant cannot be approximated within any constant factor in polynomial time unless P = NP.

Cite as

Saeed Odak, Jonathan Rollin, and Torben Scheele. On 2-Layer k-Matching-Planar Graphs. In 34th International Symposium on Graph Drawing and Network Visualization (GD 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 396, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{odak_et_al:LIPIcs.GD.2026.15,
  author =	{Odak, Saeed and Rollin, Jonathan and Scheele, Torben},
  title =	{{On 2-Layer k-Matching-Planar Graphs}},
  booktitle =	{34th International Symposium on Graph Drawing and Network Visualization (GD 2026)},
  pages =	{15:1--15:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-452-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{396},
  editor =	{L\"{o}ffler, Maarten and Miksch, Silvia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2026.15},
  URN =		{urn:nbn:de:0030-drops-279108},
  doi =		{10.4230/LIPIcs.GD.2026.15},
  annote =	{Keywords: pathwidth, k-matching-planar graph, 2-layer drawings, NP-hardness, k-planar graph, one-sided graph drawing}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2025.26

Geometric Spanners of Bounded Tree-Width

Authors: Kevin Buchin, Carolin Rehs, and Torben Scheele

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

Abstract

Given a point set P in the Euclidean space, a geometric t-spanner G is a graph on P such that for every pair of points, the shortest path in G between those points is at most a factor t longer than the Euclidean distance between those points. The value t ≥ 1 is called the dilation of G. Commonly, the aim is to construct a t-spanner with additional desirable properties. In graph theory, a powerful tool to admit efficient algorithms is bounded tree-width. We therefore investigate the problem of computing geometric spanners with bounded tree-width and small dilation t. Let d be a fixed integer and P ⊂ ℝ^d be a point set with n points. We give a first algorithm to compute an 𝒪(n/k^{d/(d-1)})-spanner on P with tree-width at most k. The dilation obtained by the algorithm is asymptotically worst-case optimal for graphs with tree-width k: We show that there is a set of n points such that every spanner of tree-width k has dilation 𝒪(n/k^{d/(d-1)}). We further prove a tight dependency between tree-width and the number of edges in sparse connected planar graphs, which admits, for point sets in ℝ², a plane spanner with tree-width at most k and small maximum vertex degree. Finally, we show an almost tight bound on the minimum dilation of a spanning tree of n equally spaced points on a circle.

Cite as

Kevin Buchin, Carolin Rehs, and Torben Scheele. Geometric Spanners of Bounded Tree-Width. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 26:1-26:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SoCG.2025.26,
  author =	{Buchin, Kevin and Rehs, Carolin and Scheele, Torben},
  title =	{{Geometric Spanners of Bounded Tree-Width}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{26:1--26:15},
  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.26},
  URN =		{urn:nbn:de:0030-drops-231786},
  doi =		{10.4230/LIPIcs.SoCG.2025.26},
  annote =	{Keywords: Computational Geometry, Geometric Spanner, Tree-width}
}

Search Results

Documents authored by Scheele, Torben

On 2-Layer k-Matching-Planar Graphs

Abstract

Cite as

Geometric Spanners of Bounded Tree-Width

Abstract

Cite as

Thanks for your feedback!

Could not send message