A center transversal theorem for hyperplanes and applications to graph drawing

DOI10.1007/s00454-012-9464-yzbMath1264.52015OpenAlexW2020827550MaRDI QIDQ1942307

Stefan Langerman, Vida Dujmović

Publication date: 18 March 2013

Published in: Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00454-012-9464-y

zbMATH Keywords

Erdős-Szekeres theoremgraph drawingline arrangementshyperplane arrangementspartitioning problemscenterpoint theoremcenter transversal theoremham-sandwich cut theoremsame-type lemma

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Related Items

A survey of mass partitions, Balanced convex partitions of lines in the plane, Computing balanced convex partitions of lines, On grids in point-line arrangements in the plane, Aligned Drawings of Planar Graphs, On Grids in Point-Line Arrangements in the Plane

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A deterministic view of random sampling and its use in geometry
• How to draw a planar graph on a grid
• Construction of \(\epsilon\)-nets
• Characterization of unlabeled level planar trees
• A polynomial bound for untangling geometric planar graphs
• Rectilinear planar layouts and bipolar orientations of planar graphs
• A generalization of the ham sandwich theorem
• Crossing families
• On Graphs Supported by Line Sets
• An Extension of the Ham Sandwich Theorem
• Towards an implementation of the 3D visibility skeleton
• An Optimal-Time Algorithm for Slope Selection
• Algèbre
• Embedding planar graphs at fixed vertex locations