A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing
- PDF / 569,561 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 37 Downloads / 161 Views
A Center Transversal Theorem for Hyperplanes and Applications to Graph Drawing Vida Dujmovi´c · Stefan Langerman
Received: 29 August 2011 / Revised: 21 March 2012 / Accepted: 15 April 2012 / Published online: 26 September 2012 © Springer Science+Business Media, LLC 2012
Abstract Motivated by an open problem from graph drawing, we study several partitioning problems for line and hyperplane arrangements. We prove a ham-sandwich cut theorem: given two sets of n lines in R2 , there√is a line such that in both line sets, for both halfplanes delimited by , there are n lines which pairwise intersect in that halfplane, and this bound is tight; a centerpoint theorem: for any set of √n lines there is a point such that for any halfplane containing that point there are n/3 of the lines which pairwise intersect in that halfplane. We generalize those results in higher dimension and obtain a center transversal theorem, a same-type lemma, and a positive portion Erd˝os–Szekeres theorem for hyperplane arrangements. This is done by formulating a generalization of the center transversal theorem which applies to set functions that are much more general than measures. Back to graph drawing (and in the plane), we completely solve the open problem that motivated our search: there is no set of n labeled lines that are universal for all n-vertex labeled planar graphs. In contrast, the main result by Pach and Toth (J. Graph Theory 46(1):39–47, 2004), has, as an easy consequence, that every set of n (unlabeled) lines is universal for all n-vertex (unlabeled) planar graphs.
The preliminar version of this paper has appeared in the Proceedings of the 27th Annual ACM Symposium on Computational Geometry, SoCG, 2011. V. Dujmovi´c () School of Mathematics and Statistics, Carleton University, Ottawa, Canada e-mail: [email protected] S. Langerman Département d’Informatique, Université Libre de Bruxelles, Brussels, Belgium e-mail: [email protected]
Discrete Comput Geom (2013) 49:74–88
75
1 Introduction Consider a mapping of the vertices of a graph to distinct points in the plane and represent each edge by the closed line segment between its endpoints. Such a graph representation is a (straight-line) drawing if the only vertices that each edge intersects are its own endpoints. A crossing in a drawing is a pair of edges that intersect at some point other than a common endpoint. A drawing is crossing-free if it has no crossings. One main focus in graph drawing is finding methods to produce drawings or crossing-free drawings for a given graph with various restrictions on the position of the vertices of the graph in the plane. For instance, there is plethora of work where vertices are required to be placed on integer grid points or on parallel lines in two or three dimensions. Given a set R of n regions in the plane and an n-vertex graph G, consider a class of graph drawing problems where G needs to be drawn crossing-free by placing each vertex of G in one region of R. If such a drawing exists, then R is said to support G. The problems
Data Loading...
