IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

Outerplanar crossing numbers, circular arrangement problem, and isoparametric functions


A 2004 Preprint by É. Czabarka, O. Sykora, L. Székely, and I. Vrto

  • 2004:03
  • We extend the lower bound in [15] for the outerplanar crossing number (in other terminologies also called convex, circular and one-page book crossing number) for a more general setting. In this setting we can show a better lower bound for the outerplanar crossing number of hypercubes than the best lower bound for the planar crossing number. We exhibit further sequences of graphs, whose outerplanar crossing number exceeds by a factor of log n the planar crossing number of the graph. We study the circular arrangement problem, as a lower bound for the linear arrangement problem, in a general fashion. We obtain new lower bounds for the circular arrangement problem. All the results depend on establishing good isoperimetric functions for certain classes of graphs. For several graph families new near-tight isoperimetric functions are established.

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster
USC