Abstract order type extension and new results on the rectilinear crossing number

DOI10.1016/j.comgeo.2005.07.005zbMath1110.65019OpenAlexW2205343714WikidataQ56443310 ScholiaQ56443310MaRDI QIDQ870421

Hannes Krasser, Oswin Aichholzer

Publication date: 12 March 2007

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2005.07.005

zbMATH Keywords

numerical examplestriangulationsrectilinear crossing numbercomplete graphorder typepseudoline arrangementconvex regionsdecomposing setshappy end problemsearching for convex \(k\)-gons

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items

Two disjoint 5-holes in point sets, On the number of plane geometric graphs, On crossing-families in planar point sets, Order on order types, Extreme point and halving edge search in abstract order types, Enumerating Neighborly Polytopes and Oriented Matroids, Reprint of: Extreme point and halving edge search in abstract order types, Approximating the Rectilinear Crossing Number, Complete enumeration of small realizable oriented matroids, A Note on Universal Point Sets for Planar Graphs, On the 2-colored crossing number, A note on universal point sets for planar graphs, Unnamed Item, Matroid enumeration for incidence geometry, Faradžev Read-type enumeration of non-isomorphic CC systems, Geodesic order types, On 5-Gons and 5-Holes, On the number of order types in integer grids of small size, Crossing numbers and combinatorial characterization of monotone drawings of \(K_n\), Point sets that minimize \((\leq k)\)-edges, 3-decomposable drawings, and the rectilinear crossing number of \(K_{30}\), Improved upper bounds on the reflexivity of point sets, Clique-width of point configurations, A superlinear lower bound on the number of 5-holes, Approximating the rectilinear crossing number, Many order types on integer grids of polynomial size, On the crossing number of complete graphs

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the finding of final polynomials
• New trends in discrete and computational geometry
• On the crossing number of complete graphs
• Generation of oriented matroids --- a graph theoretical approach
• On the number of arrangements of pseudolines
• Enumerating order types for small point sets with applications
• A lower bound on the number of triangulations of planar point sets
• Two interesting oriented matroids
• Multidimensional Sorting
• Abstract order type extension and new results on the rectilinear crossing number
• Toward a theory of crossing numbers
• Crossing Number Problems
• Graph Drawing
• On the Number of Crossings in a Complete Graph
• The rectilinear crossing number of \(K_{10}\) is 62