Metraipolis › archive › dc_cd32aede1827

Product Structure Meets Track Layouts — arXiv:2608.27096

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.27096
License (as archived): CC0-1.0
Archived: 2026-10-17T19:20:11.144Z
SHA-256 of the archived text: a4cd7c2f10312d97d045aeaa68adf7bf3811b25b294652b70a5401e7f7a914ca
Stable URL of this page: https://metraipolis.com/documento/dc_cd32aede1827

How to cite

Product Structure Meets Track Layouts — arXiv:2608.27096 — arXiv (en), https://arxiv.org/abs/2608.27096 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd32aede1827 (Metraipolis archive dc_cd32aede1827, sha256 a4cd7c2f10312d97d045aeaa68adf7bf3811b25b294652b70a5401e7f7a914ca)

BibTeX

@misc{dccd32aede1827,
  title = {Product Structure Meets Track Layouts — arXiv:2608.27096},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.27096},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd32aede1827; sha256 a4cd7c2f10312d97d045aeaa68adf7bf3811b25b294652b70a5401e7f7a914ca},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.27096. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

A track layout of a graph is a partition of its vertices into linearly ordered independent sets, called tracks, such that no two edges between the same pair of tracks cross. Given a graph, the goal in this context is to determine its track number, that is, the minimum number of tracks required for the graph to admit a track layout. In this work, we present upper bounds on the track number of graphs admitting a product structure. Our main contribution is an algorithm that computes a track layout with at most $(2h+1) \cdot r \cdot tn(H)$ tracks for every subgraph of the strong product $P^h \boxtimes K_r \boxtimes H$, where $P^h$ is the $h$-th power of a path $P$, $K_r$ is the complete graph on $r$ vertices, and $H$ is a graph with track number $tn(H)$. Combined with existing product-structure results from the literature, this algorithm yields upper bounds on the track number of several graph classes. For planar graphs, the obtained bound matches the current best-known upper bound of $225$. For $1$-planar and optimal $2$-planar graphs, our algorithm yields track layouts with at most $375$ tracks, while for genus-$k$, $k$-planar, $k$-framed, $k$-map, and $k$-string graphs it provides track layouts with a number of tracks that depends solely on $k$, thus establishing new upper bounds on the track number for these graph classes. The algorithm runs in linear time for planar graphs and, more generally, in $O(n + h \cdot r \cdot t + f_t(H))$ time whenever a corresponding product-structure decomposition of the input $n$-vertex graph is provided as part of the input, where $t=tn(H)$ and $f_t(H)$ is the time needed to compute a $t$-track layout of $H$. Furthermore, our algorithm only uses elementary linked-list data structures.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-28 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2608.27096 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-17T19:16:36.841Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-08-28?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).