A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid (Q1382254): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 04:09, 5 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid |
scientific article |
Statements
A linear algorithm for 2-bend embeddings of planar graphs in the two-dimensional grid (English)
0 references
18 May 1999
0 references
It is well known that every \(n\)-vertex planar graph of maximum degree at most 4 has a drawing in the plane such that its vertices are points of the integer grid and its edges are nonintersecting paths in the grid graphs. Moreover, each edge may be required to have at most four bends. In this paper, a linear time algorithm is presented which produces such a drawing with at most two bends per edge (with the only exception among connected graphs being the octahedron for which three bends are necessary), and so that the number of bends is at most \(7n/3\). Moreover, the drawing can be enclosed in a rectangle with area \((n+1)^2\).
0 references
planar graph
0 references
drawing
0 references
grid graphs
0 references
linear time algorithm
0 references