Title
Drawing Graphs on Rectangular Grids with at most 2
Bends per Edge
Author
-
Publication
DISAM, vol. 65, 1995, pp. 75-89
Source
-
Classification
-
not available
Keywords
-
not available
-
-
Given an undirected graph G=(V,E) with n vertices
of maximum degree 4. It is well known that such a
graph can be embedded in a rectangular grid with at
most 2n columns and 2n rows such that any edge is
embedded with at most 5 bends. On the other hand, two
is a lower bound on the maximum number of bends per
embed ded edge since the graph K5 cannot be embedded
with less than 2 bends per embedded edg e. We present
an algorithm that computes an embedding for arbitrary
graphs with n vertices of maximum degree 4 in a grid
with exactly 2n columns and 2n rows such that all
edges are embedded with at most 2 bends per edge.
