Source-linked AI summary
Product Structure Meets Track Layouts
Michael A. Bekos, Giordano Da Lozzo, Petr Hliněný, Michael Kaufmann
TL;DR
The paper seeks upper bounds on track number for graph classes admitting product structure, extending a perspective previously not formulated explicitly in product-structure terms. It introduces an algorithm achieving a bound of (2h+1)·r·tn(H) for subgraphs of P^h ⊠K_r ⊠H, with broad class-specific consequences and efficient running time. The resulting bounds include 225 for planar graphs, 375 for 1-planar and optimal 2-planar graphs, and bounds depending only on k for several k-parameterized classes.
Problem
Because determining track number is NP-hard, the paper studies upper bounds for graph classes with product structure, addressing the previously unformulated connection between product-structure results and track number.
Method
The paper develops an algorithm that constructs track layouts for subgraphs of P^h ⊠K_r ⊠H from a t-track layout of H.
Results
The algorithm guarantees tn(G) ≤ (2h+1)·r·tn(H), matching the best-known planar bound of 225 and yielding 375 tracks for 1-planar and optimal 2-planar graphs.
Takeaways & Limitations
Product-structure theorems can be translated into efficient track-number upper bounds, including bounds depending solely on k for genus-k, k-planar, k-framed, k-map, and k-string graphs.
Takeaways & Limitations
Improving the upper bound of 225 for planar graphs remains an open problem, and better bounds for planar 3-trees would affect several product-structured classes.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses track-number bounds beyond planarity by making product structure explicit and introducing an algorithm for subgraphs of strong products. It obtains broad class-specific bounds, including 225 for planar graphs and 375 for 1-planar and optimal 2-planar graphs, with efficient implementation.
- Motivation: Track layouts partition vertices into linearly ordered independent sets whose edges between each track pair do not cross.The minimum number of tracks is the track number tn(G).
- Motivation: Determining track number is NP-hard, motivating upper bounds for specific graph classes.Planar graphs have current best-known upper bound 225.
- Product structure: Every planar graph is a subgraph of P ⊠K3 ⊠H for a path, a three-vertex clique, and a planar 3-tree.This product-structure perspective has also been extended to graph classes beyond planarity.
- Contribution: The main algorithm constructs at most (2h + 1) · r · t tracks for subgraphs of P^h ⊠K_r ⊠H when H has a t-track layout.The corresponding theorem gives tn(G) ≤ (2h+1)·r·tn(H).
- Algorithmic implementation: The algorithm runs in linear time for planar graphs and uses no complex data structures.More generally, its running time is O(n + h · r · t + f_t(H)) when a suitable product decomposition is available or computable in linear time.
- Consequences: 225 tracks for planar graphs matches the current best-known bound, while 375 tracks suffice for 1-planar and optimal 2-planar graphs.For several other classes, the resulting number of tracks depends solely on k.
2 Preliminaries
The preliminaries define graph powers, graph classes, strong products, and track layouts. They also describe strong products through copies of one factor and classify product edges into horizontal, vertical, forward, and backward types.
- Basic definitions: The i-th power G^i preserves G's vertices and joins distinct vertices exactly when their distance in G is at most i.Consequently, G is a subgraph of G^i.
- Graph classes: A planar graph embeds in the plane without edge crossings, while genus-k and k-planar graphs generalize embeddings and crossing constraints.An optimal k-planar graph has the maximum number of edges among n-vertex k-planar graphs.
- Product structure: The strong product X ⊠Y has vertex set V(X) × V(Y), with adjacency arising from an edge in one factor, or edges in both factors.The product can equivalently be built from copies of X indexed by Y or copies of Y indexed by X.
- Product structure: In the copy-based construction, edges are added within copies and between copies according to corresponding, forward, and backward adjacency patterns.These rules connect vertices sharing one coordinate and vertices whose coordinates are adjacent in the two factors.
- Product structure: The product edges divide into horizontal, vertical, forward, and backward sets.This partition supports the later analysis of crossings between edge types.
- Track layouts: A track is an ordered independent vertex set, and a track layout is an ordered partition with no X-crossings.An X-crossing occurs when endpoint orders are opposite on two tracks.
3 Track Number of Graphs Having a Product Structure
The section develops track-number bounds for subgraphs of strong products by reusing track layouts of a factor graph and assigning path-power layers to distinct track classes.
- Path products: A 3t-track layout is constructed for P ⊠ H by placing copies of a t-track layout of H according to indices modulo 3.Vertices in layers with different residues use different tracks, while same-residue copies share tracks in path order.
- Path products: The construction avoids X-crossings by separately checking horizontal, vertical, forward, and backward edges and then checking pairs from distinct edge sets.The proof uses matching orders, the inherited track layout of H, and consistent ordering between path layers.
- Path products: (2h + 1) · tn(H) bounds the track number of every subgraph G ⊆ P^h ⊠ H.The construction uses χ(P^2h) = 2h + 1.
- Consequences: Lemmas 2 and 3 together imply Theorem 1, and the bounds in Table 2 follow as corollaries of cited product-structure theorems.Thus product decompositions can be converted into track-number upper bounds.
4 Implementation Details
The implementation constructs tracks by grouping vertices into coordinate-based buckets, ordering them through scans, and concatenating lists. Applied recursively to product decompositions, it produces at most (2h + 1) · r · t tracks in O(n + h · r · t + ft(H)) time.
- Bucket construction: Vertices are assigned to buckets B_i,a according to their path index i and the track a containing their H-coordinate.Each bucket contains vertices with ind_P(v.x) = i and t_L(v.y) = a.
- Track ordering: Buckets are concatenated into tracks using the index (2h + 1) · a + (i mod (2h + 1)), producing lexicographic order by path position and inherited H-track order.Vertices from path copies with matching residues share tracks, while earlier path copies precede later ones.
- Algorithm inputs and outputs: The algorithm takes G ⊆ P^h ⊠ H, a t-track layout of H, and h, and outputs a (2h + 1)t-track assignment.Its explicit input and output are given in Algorithm 1.
- Bucket construction: Bucket vertices inherit the order of their H-coordinates by scanning each track of H, avoiding a separate sorting step.Vertices are appended as tracks T_a are scanned, so each bucket is automatically ordered.
- Data structures: The construction represents tracks, lists, and buckets as linked lists, making appending and concatenation constant-time operations.Only nonempty buckets are created, and the method uses no complex data structures.
- Complexity and specialization: The full product-decomposition algorithm runs in O(n + h · r · t + ft(H)) time and yields at most (2h + 1) · r · t tracks.For planar graphs, h = 1, r = 3, and a 25-track layout of H gives a linear-time 225-track layout.
5 Conclusions
The paper extends track-layout bounds through product structure and provides a simple, linear-time framework for planar graphs. It closes by identifying improvements to k-tree, planar 3-tree, and planar-graph bounds as open problems.
- Contributions: The framework establishes new track-number bounds for genus-k, k-planar, k-framed, k-map, and k-string graph families.These families are among the broad classes addressed through product structure.
- Contributions: The resulting algorithm uses no complex data structures and runs in linear time for planar graphs.The conclusion characterizes the framework as both elegant and insightful while emphasizing its algorithmic simplicity.
- Open problems: Improving the upper bound of (k + 1)(2k+1 − 2)k for k-trees would immediately improve corresponding bounds for most listed graph families.The k = 3 planar case is especially relevant because several classes use planar 3-tree product structures.
- Open problems: Improving the current upper bound of 25 for planar 3-trees would significantly affect several graph classes expressed using planar 3-tree product structures.The conclusion identifies this as a particularly consequential direction for k = 3.
- Open problems: The paper matches the upper bound of 225 for planar graphs, but improving that bound remains an unresolved challenge.The authors describe further improvement as elusive and the problem as difficult and fundamental.