Crossing-Free Subgraphs
From MaRDI portal
Publication:3967549
DOI10.1016/S0304-0208(08)73484-4zbMath0502.05021OpenAlexW13988344MaRDI QIDQ3967549
No author found.
Publication date: 1982
Published in: Theory and Practice of Combinatorics - A collection of articles honoring Anton Kotzig on the occasion of his sixtieth birthday (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/s0304-0208(08)73484-4
Extremal problems in graph theory (05C35) Enumeration in graph theory (05C30) Planar graphs; geometric and topological aspects of graph theory (05C10)
Related Items
Number of Crossing-Free Geometric Graphs vs. Triangulations, Convex Polygons in Geometric Triangulations, An upper bound for the number of rectangulations of a planar point set, Shallow Minors, Graph Products, and Beyond-Planar Graphs, Unnamed Item, Graph product structure for non-minor-closed classes, Book embeddings and crossing numbers, String graphs and incomparability graphs, Simultaneous Embeddings with Few Bends and Crossings, Crossing patterns of segments, SIMULTANEOUS ARITHMETIC PROGRESSIONS ON ALGEBRAIC CURVES, Sequences of spanning trees and a fixed tree theorem, General lower bounds for the minor crossing number of graphs, A Bipartite Strengthening of the Crossing Lemma, A Census of Plane Graphs with Polyline Edges, 2-point site Voronoi diagrams, A better upper bound on the number of triangulations of a planar point set, Configurations of non-crossing rays and related problems, Crossing number, pair-crossing number, and expansion, The Crossing Number of the Cone of a Graph, On the intersections of non-homotopic loops, Counting triangle crossings and halving planes, Counting carambolas, Computing colourful simplicial depth and Median in \(\mathbb{R}_2\), On the number of plane geometric graphs, Convex Polygons in Geometric Triangulations, A lower bound for the optimal crossing-free Hamiltonian cycle problem, Onion polygonizations, Non-homotopic loops with a bounded number of pairwise intersections, On the number of edges of separated multigraphs, A crossing lemma for Jordan curves, Sumsets of semiconvex sets, On the number of anchored rectangle packings for a planar point set, On the Number of Anchored Rectangle Packings for a Planar Point Set, The crossing number of twisted graphs, Anchored expansion, speed and the Poisson-Voronoi tessellation in symmetric spaces, On the number of simplicial complexes in \(\mathbb{R}^ d\), Fan-crossing free graphs and their relationship to other beyond-planar graphs, On topological graphs with at most four crossings per edge, On bipartite distinct distances in the plane, Trapezoidal diagrams, upward triangulations, and prime Catalan numbers, Crossings between non-homotopic edges, Bounded degree conjecture holds precisely for \(c\)-crossing-critical graphs with \(c \le 12\), A crossing lemma for multigraphs, Crossings in grid drawings, Progress on Dirac's conjecture, Degrees of nonlinearity in forbidden 0-1 matrix problems, The Mathematics of Ferran Hurtado: A Brief Survey, Crossing-number critical graphs have bounded path-width, On the number of touching pairs in a set of planar curves, Graphs that admit right angle crossing drawings, The Bundled Crossing Number, Approximating the Rectilinear Crossing Number, Distinct distances on non-ruled surfaces and between circles, On crossing numbers of geometric proximity graphs, On numbers of pseudo-triangulations, On 2-site Voronoi diagrams under geometric distance functions, On the degenerate crossing number, On distinct sums and distinct distances., Planar crossing numbers of graphs of bounded genus, An incidence theorem in higher dimensions, A successful concept for measuring non-planarity of graphs: The crossing number., Many Touchings Force Many Crossings, The number of crossings in multigraphs with no empty lens, Crossing numbers and stress of random graphs, Efficient Generation of Different Topological Representations of Graphs Beyond-Planarity, Characterisations and examples of graph classes with bounded expansion, A primer of the Euclidean Steiner problem, On degree properties of crossing-critical families of graphs, Robust Tverberg and Colourful Carathéodory Results via Random Choice, Counting Plane Graphs with Exponential Speed-Up, How to find Steiner minimal trees in Euclidean \(d\)-space, Gray code enumeration of plane straight-line graphs, On the decay of crossing numbers, Crossing number for graphs with bounded pathwidth, Flips in planar graphs, A bipartite strengthening of the crossing Lemma, On degrees in random triangulations of point sets, Two-Planar Graphs Are Quasiplanar, On the complexity of the \(k\)-level in arrangements of pseudoplanes, Unnamed Item, Unnamed Item, Structure and generation of crossing-critical graphs, Unnamed Item, Graphs that Admit Right Angle Crossing Drawings, On planar intersection graphs with forbidden subgraphs, Monotone paths in geometric triangulations, Biplanar crossing numbers. II. Comparing crossing numbers and biplanar crossing numbers using the probabilistic method, Testing gap \(k\)-planarity is NP-complete, Planar point sets determine many pairwise crossing segments, On edges crossing few other edges in simple topological complete graphs, A survey of graphs with known or bounded crossing numbers, A Szemerédi-Trotter type theorem in \(\mathbb R^4\), Degenerate crossing numbers, Penny-packing and two-dimensional codes, Twenty years of progress of \(\mathrm{JCDCG}^3\), Graphs drawn with few crossings per edge, Many touchings force many crossings, The number of crossings in multigraphs with no empty lens, Extremal problems on triangle areas in two and three dimensions, On polygons enclosing point sets. II, Approximating the rectilinear crossing number, A new lower bound on the maximum number of plane graphs using production matrices, Quasi-planar Graphs, $$\textit{\textbf{k}}$$-Planar Graphs, Crossing lemma for the odd-crossing number, Which crossing number is it anyway?, Crossings Between Non-homotopic Edges, 2-Layer k-Planar Graphs, Geometric biplane graphs. I: Maximal graphs, Lower bounds on the maximum number of non-crossing acyclic graphs, Graph minors and the crossing number of graphs, On counting triangulations in \(d\) dimensions, Counting triangulations and other crossing-free structures via onion layers, A crossing lemma for multigraphs
