Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas

DOI10.1137/S0097539700373520zbMath1029.68160OpenAlexW2069815120WikidataQ57255590 ScholiaQ57255590MaRDI QIDQ4706191

Sudipto Guha, Baruch Schieber, Guy Even

Publication date: 19 June 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539700373520

zbMATH Keywords

approximation algorithmcrossing numbergraph drawingVLSI layout

Mathematics Subject Classification ID

Hardware implementations of nonnumerical algorithms (VLSI algorithms, etc.) (68W35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Crossing number, pair-crossing number, and expansion, Inserting Multiple Edges into a Planar Graph, The crossing number of a projective graph is quadratic in the face–width, Approximating the Rectilinear Crossing Number, Orthogonal drawings and crossing numbers of the Kronecker product of two cycles, Exact crossing number parameterized by vertex cover, Planar crossing numbers of graphs of bounded genus, Crossing number additivity over edge cuts, Approximating the Crossing Number of Toroidal Graphs, Crossing minimization in perturbed drawings, A tighter insertion-based approximation of the crossing number, A Bottleneck Matching Problem with Edge-Crossing Constraints, The Crossing Number of Graphs: Theory and Computation, Approximating the rectilinear crossing number, Separator-based graph embedding into multidimensional grids with small edge-congestion