Toroidal grid minors and stretch in embedded graphs

DOI10.1016/j.jctb.2019.05.009zbMath1430.05122arXiv1403.1273OpenAlexW2377835982WikidataQ127728187 ScholiaQ127728187MaRDI QIDQ2284733

Markus Chimani, Gelasio Salazar, Petr Hliněný

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

crossing numbergraph embeddingstoroidal gridstretchcompact surfacesedge-width

Mathematics Subject Classification ID

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

Related Items

Parameterized analysis and crossing minimization problems, Inserting Multiple Edges into a Planar Graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Planar crossing numbers of graphs of bounded genus
• Crossing number and weighted crossing number of near-planar graphs
• Vertex insertion approximates the crossing number of apex graphs
• Graph minors. XX: Wagner's conjecture
• Locally planar graphs are 5-choosable
• Graph minors. VII: Disjoint paths on a surface
• The crossing number of \(C_3\times C_n\)
• Five-coloring maps on surfaces
• Trees in triangulations
• Coloring graphs without short non-bounding cycles
• Graphs on the torus and geometry of numbers
• Grid minors of graphs on the torus
• Inserting an edge into a planar graph
• Drawings of \(C_m\times C_n\) with one disjoint family. II
• Separating and nonseparating disjoint homotopic cycles in graph embeddings
• A tighter insertion-based approximation of the crossing number
• Crossing number is hard for cubic graphs
• Computing the Stretch of an Embedded Graph
• Disjoint paths, planarizing cycles, and spanning walks
• The Minor Crossing Number
• The crossing number of a projective graph is quadratic in the face–width
• On the Crossing Number of Almost Planar Graphs
• On the crossing numbers of products of cycles and graphs of order four
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Computing the orientable genus of projective graphs
• [https://portal.mardi4nfdi.de/wiki/Publication:4888117 The crossing number ofC5 �Cn]
• Approximating the Crossing Number of Toroidal Graphs
• Improved algorithms for min cut and max flow in undirected planar graphs
• PLANAR CROSSING NUMBERS OF GRAPHS EMBEDDABLE IN ANOTHER SURFACE