Toward a theory of crossing numbers

DOI10.1016/S0021-9800(70)80007-2zbMath0187.20803MaRDI QIDQ5578799

William T. Tutte

Publication date: 1970

Published in: Journal of Combinatorial Theory (Search for Journal in Brave)

zbMATH Keywords

topology

Related Items (76)

Bad drawings of small complete graphs ⋮ On pseudo-disk hypergraphs ⋮ Crossing number, pair-crossing number, and expansion ⋮ Eliminating higher-multiplicity intersections. III. Codimension 2 ⋮ Geometric graphs with no self-intersecting path of length three ⋮ The complexity of planarity testing ⋮ Boolean approach to planar embeddings of a graph ⋮ On the number of edges of separated multigraphs ⋮ A crossing lemma for Jordan curves ⋮ On the embeddability of skeleta of spheres ⋮ The \(\mathbb{Z}_2\)-genus of Kuratowski minors ⋮ A new approach to the linearity of testing planarity of graphs ⋮ On the strong Hanani-Tutte theorem ⋮ Abstract order type extension and new results on the rectilinear crossing number ⋮ Unified Hanani-Tutte theorem ⋮ Parameterized analysis and crossing minimization problems ⋮ The crossing number of locally twisted cubes \(L T Q_n\) ⋮ Genetic algorithms for drawing bipartite graphs ⋮ Towards the Hanani-Tutte Theorem for Clustered Graphs ⋮ Geometria combinatoria e geometrie finite ⋮ Removing even crossings ⋮ Monotone Crossing Number ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ Simple realizability of complete abstract topological graphs simplified ⋮ Disproof of a conjecture by Erdős and Guy on the crossing number of hypercubes ⋮ Embedding dimensions of simplicial complexes on few vertices ⋮ Removing Even Crossings on Surfaces ⋮ Hardness of embedding simplicial complexes in \(\mathbb R^d\) ⋮ Clustered planarity testing revisited ⋮ Crossing-number critical graphs have bounded path-width ⋮ Hanani-Tutte for radial planarity. II ⋮ On the Size of Planarly Connected Crossing Graphs ⋮ A Direct Proof of the Strong Hanani–Tutte Theorem on the Projective Plane ⋮ Embeddings of \(k\)-complexes into \(2k\)-manifolds ⋮ On Codimension One Embedding of Simplicial Complexes ⋮ Conflict-free coloring of intersection graphs of geometric objects ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ On String Graph Limits and the Structure of a Typical String Graph ⋮ A successful concept for measuring non-planarity of graphs: The crossing number. ⋮ Orthogonal drawings of graphs for the automation of VLSI circuit design ⋮ Obstacle Numbers of Planar Graphs ⋮ Many Touchings Force Many Crossings ⋮ Level planarity: transitivity vs. even crossings ⋮ Some provably hard crossing number problems ⋮ Note on the pair-crossing number and the odd-crossing number ⋮ Crossing minimization in perturbed drawings ⋮ Pfaffian graphs, \(T\)-joins and crossing numbers ⋮ Boolean planarity characterization of graphs ⋮ On grids in topological graphs ⋮ Crossing minimization in perturbed drawings ⋮ Odd crossing number and crossing number are not the same ⋮ Crossing numbers of graphs with rotation systems ⋮ Conflict-free coloring of string graphs ⋮ Unnamed Item ⋮ Hanani-Tutte for approximating maps of graphs ⋮ The $\mathbb{Z}_2$-genus of Kuratowski minors ⋮ On Boolean characterizations of planarity and planar embeddings of graphs ⋮ A note on the parity of the number of crossings of a graph ⋮ Towards an implementation of the 3D visibility skeleton ⋮ Adjacent Crossings Do Matter ⋮ Planar diagrams for local invariants of graphs in surfaces ⋮ Many touchings force many crossings ⋮ The Crossing Number of Graphs: Theory and Computation ⋮ A sharp threshold phenomenon in string graphs ⋮ Hanani-Tutte and Monotone Drawings ⋮ Removing even crossings on surfaces ⋮ An evolutionary formulation of the crossing number problem ⋮ Finding Minors in Graphs with a Given Path Structure ⋮ Level-planarity: transitivity vs. even crossings ⋮ Which crossing number is it anyway? ⋮ Ensemble convexes dans les graphes. I: Théoremes de Helly et de Radon pour graphes et surfaces ⋮ An upper bound for the crossing number of augmented cubes ⋮ A characterization of planar graphs by Trémaux orders ⋮ Coloring intersection hypergraphs of pseudo-disks ⋮ Almost all string graphs are intersection graphs of plane convex sets ⋮ On the crossing number of complete graphs

This page was built for publication: Toward a theory of crossing numbers