Drawings of graphs on surfaces with few crossings

DOI10.1007/BF02086611zbMath0854.68074MaRDI QIDQ1920424

Imrich Vrt'o, Ondrej Sýkora, László A. Székely, Farhad Shahrokhi

Publication date: 20 October 1996

Published in: Algorithmica (Search for Journal in Brave)

zbMATH Keywords

polynomial-time algorithmcrossing numbertopological graph theory

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Structure of Graphs with Locally Restricted Crossings, A successful concept for measuring non-planarity of graphs: The crossing number., Turán’s Brick Factory Problem: The Status of the Conjectures of Zarankiewicz and Hill

Cites Work

• Unnamed Item
• Unnamed Item
• On crossing numbers of hypercubes and cube connected cycles
• Multilayer grid embeddings for VLSI
• Edge crossings in drawings of bipartite graphs
• The crossing number of a graph on a compact 2-manifold
• Fast approximation algorithms for multicommodity flow problems
• A lower bound for crossing numbers of graphs with application to \(K_n\),\(K_{pq}\)g, and \(Q(d)\)
• Crossing Number is NP-Complete
• The maximum concurrent flow problem
• On stable crossing numbers
• An infinite family of octahedral crossing numbers
• Fast Approximation Schemes for Convex Programs with Many Blocks and Coupling Constraints
• Faster Approximation Algorithms For the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts
• On Canonical Concurrent Flows, Crossing Number and Graph Expansion
• The toroidal crossing number of the complete graph
• The toroidal crossing number of Km,n
• The crossing number of K5,n
• Crossing Number Problems