| Canadian Conference on Computational Geometry held in Montréal, Québec, Canada. Minimum-Bend Graph Drawing in Other Grids (2008) | |||||||||||||||
Abstract | |||||||||||||||
| What is the best worst-case guarantee one can make on the number of bends required to embed a graph into a particular grid, in particular, the hexagonal and octagonal grids? A grid pointdrawing of a graph maps each vertex to a unique point of the grid, and maps each edge to a path in the grid connecting the endpoints; the paths are allowed to intersect at common endpoints and at proper crossings (points at which two or more paths meet but do not bend), but must be edge-disjoint. Such a drawing exists only for graphs whose maximum vertex degree is at most the maximum degree ∆ of a point in the grid. The goal of this problem is to obtain a bound of the form “every graph on n vertices of maximum vertex degree ∆ has a grid point-drawing with at most f(n) bends ” for various grids. In the usual square grid, 2D points have integral coordinates and an edge connects every two points at Euclidean distance exactly 1, so ∆ = 4. Here it is known that every graph with maximum vertex degree at most ∆ = 4 has a square-grid point-drawing with at most 2n + 4 bends [BK98, LMS98]. The “8-way square grid ” has the same set of points but connects two points at Euclidean distance either 1 or √ 2—that is, it draws two diagonals within each square cell—so ∆ = 8. In this case, Biedl can prove an upper bound of 6n+O(1) bounds, and the proof is not too difficult. Is there a better bound? The three tilings of the plane by identical regular polygons are the square grid, the triangular grid ( ∆ = 6), and the hexagonal grid ( ∆ = 3). For the triangular grid, Biedl can prove an upper bound of | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||