Toroidal grid minors and stretch in embedded graphs

DOI10.1016/J.JCTB.2019.05.009MaRDI QIDQ2284733zbMATH OpenOpenAlexWikidataFDO

Authors Markus Chimani, Petr Hliněný, Gelasio Salazar

Publication date 15 January 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.1273

zbMATH Keywords

compact surfacescrossing numberedge-widthgraph embeddingsstretchtoroidal grid

Mathematics Subject Classification ID

Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)

Abstract: We investigate the toroidal expanse of an embedded graph G, that is, the size of the largest toroidal grid contained in G as a minor. In the course of this work we introduce a new embedding density parameter, the stretch of an embedded graph G, and use it to bound the toroidal expanse from above and from below within a constant factor depending only on the genus and the maximum degree. We also show that these parameters are tightly related to the planar crossing number of G. As a consequence of our bounds, we derive an efficient constant factor approximation algorithm for the toroidal expanse and for the crossing number of a surface-embedded graph with bounded maximum degree.

Recommendations

• Grid minors of graphs on the torus
• Structure of graphs with locally restricted crossings
• Approximating the Crossing Number of Toroidal Graphs
• Computing the stretch of an embedded graph
• Embedding grids in surfaces

Cites work

• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Approximating the crossing number of graphs embeddable in any orientable surface
• Approximating the Crossing Number of Toroidal Graphs
• Bounding the crossing number of a graph in terms of the crossing number of a minor with small maximum degree
• Coloring graphs without short non-bounding cycles
• Computing the orientable genus of projective graphs
• Computing the stretch of an embedded graph
• Crossing number and weighted crossing number of near-planar graphs
• Crossing number is hard for cubic graphs
• Disjoint paths, planarizing cycles, and spanning walks
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• Five-coloring maps on surfaces
• Graph minors. VII: Disjoint paths on a surface
• Graph minors. XX: Wagner's conjecture
• Graphs on surfaces
• Graphs on the torus and geometry of numbers
• Grid minors of graphs on the torus
• scientific article; zbMATH DE number 412172 (Why is no real title available?)
• scientific article; zbMATH DE number 5130834 (Why is no real title available?)
• scientific article; zbMATH DE number 5506235 (Why is no real title available?)
• Improved algorithms for \textsc{Min-cut} and \textsc{Max-flow} in undirected planar graphs
• Inserting an edge into a planar graph
• Locally planar graphs are 5-choosable
• On the Crossing Number of Almost Planar Graphs
• On the crossing numbers of products of cycles and graphs of order four
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE
• Planar crossing numbers of graphs of bounded genus
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• The crossing number of \(C_3\times C_n\)
• The crossing number of a projective graph is quadratic in the face–width
• The crossing number ofC5 �Cn
• The Minor Crossing Number
• Trees in triangulations
• Vertex insertion approximates the crossing number of apex graphs

Cited in

(4)

• Grid minors of graphs on the torus
• The grid theorem for vertex-minors
• Parameterized analysis and crossing minimization problems
• Inserting Multiple Edges into a Planar Graph

This page was built for publication: Toroidal grid minors and stretch in embedded graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2284733)