Structure of $k$-Matching-Planar Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909846707634176 |
|---|---|
| author | Hendrey, Kevin Karol, Nikolai Wood, David R. |
| author_facet | Hendrey, Kevin Karol, Nikolai Wood, David R. |
| contents | For $k \geqslant 0$, we define a simple topological graph $G$ (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be $k$-matching-planar if for every edge $e \in E(G)$, every matching amongst the edges of $G$ that cross $e$ has size at most $k$. The class of $k$-matching-planar graphs is a significant generalisation of many other existing beyond planar graph classes, including $k$-planar graphs. We prove that every simple topological $k$-matching-planar graph is isomorphic to a subgraph of the strong product of a graph with bounded treewidth and a path. This result qualitatively extends the planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] and recent product structure theorems for other beyond planar graph classes. Using this result, we deduce that the class of simple topological $k$-matching-planar graphs has several attractive properties, making it the broadest class of simple beyond planar graphs in the literature that has these properties. All of our results about simple topological $k$-matching-planar graphs generalise to the non-simple setting, where the maximum number of pairwise crossing edges incident to a common vertex becomes relevant.
The paper introduces several tools and results of independent interest. We show that every simple topological $k$-matching-planar graph admits an edge-colouring with $\mathcal{O}(k^{3}\log k)$ colours such that monochromatic edges do not cross. As a key ingredient of the proof of our main product structure theorem, we introduce the concept of weak shallow minors, which subsume and generalise shallow minors, a key concept in graph sparsity theory. We also establish upper bounds on the treewidth of graphs with well-behaved circular drawings that qualitatively generalise several existing results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_22395 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Structure of $k$-Matching-Planar Graphs Hendrey, Kevin Karol, Nikolai Wood, David R. Combinatorics Discrete Mathematics 68R10, 05C83, 05C10 For $k \geqslant 0$, we define a simple topological graph $G$ (that is, a graph drawn in the plane such that every pair of edges intersect at most once, including endpoints) to be $k$-matching-planar if for every edge $e \in E(G)$, every matching amongst the edges of $G$ that cross $e$ has size at most $k$. The class of $k$-matching-planar graphs is a significant generalisation of many other existing beyond planar graph classes, including $k$-planar graphs. We prove that every simple topological $k$-matching-planar graph is isomorphic to a subgraph of the strong product of a graph with bounded treewidth and a path. This result qualitatively extends the planar graph product structure theorem of Dujmović, Joret, Micek, Morin, Ueckerdt, and Wood [J. ACM 2020] and recent product structure theorems for other beyond planar graph classes. Using this result, we deduce that the class of simple topological $k$-matching-planar graphs has several attractive properties, making it the broadest class of simple beyond planar graphs in the literature that has these properties. All of our results about simple topological $k$-matching-planar graphs generalise to the non-simple setting, where the maximum number of pairwise crossing edges incident to a common vertex becomes relevant. The paper introduces several tools and results of independent interest. We show that every simple topological $k$-matching-planar graph admits an edge-colouring with $\mathcal{O}(k^{3}\log k)$ colours such that monochromatic edges do not cross. As a key ingredient of the proof of our main product structure theorem, we introduce the concept of weak shallow minors, which subsume and generalise shallow minors, a key concept in graph sparsity theory. We also establish upper bounds on the treewidth of graphs with well-behaved circular drawings that qualitatively generalise several existing results. |
| title | Structure of $k$-Matching-Planar Graphs |
| topic | Combinatorics Discrete Mathematics 68R10, 05C83, 05C10 |
| url | https://arxiv.org/abs/2507.22395 |