Maximum Rectilinear Crossing Numbers of Polyhex Graphs

Elie Feder1, Heiko Harborth2
1Department of Mathematics and Computer Science, Kingsborough Community College-CUNY, Brooklyn, NY, USA.
2Diskrete Mathematik, Technische Universitat, Braunschweig, Germany

Abstract

A polyhex is a set of hexagons of the Euclidean tessellation of the plane by congruent regular hexagons. Then, a polyhex graph has the vertex points of the hexagons as its vertices and the sides of the hexagons as its edges. A rectilinear drawing of a graph in the plane uses straight line segments for the edges. Partial results are given for the maximum number of crossings over all rectilinear drawings of a polyhex graph