Convex Drawings of 3-Connected Plane Graphs |
| |
Authors: | Nicolas Bonichon Stefan Felsner Mohamed Mosbah |
| |
Affiliation: | (1) LaBRI, Universite Bordeaux-1, 351 cours de la Liberation, 33405, Talence Cedex, France;(2) Technische Universitat Berlin, Institut fur Mathematik, MA 6-1, Strasse des 17. Juni 136, 10623, Berlin, Germany |
| |
Abstract: | We use Schnyder woods of 3-connected planar graphs to produce convex straight-line drawings
on a grid of size
The parameter
depends on the Schnyder wood used for the drawing. This parameter is in the range
The algorithm is a refinement of the face-counting algorithm; thus, in particular, the size of the grid is at most
The above bound on the grid size simultaneously matches or improves all previously known bounds for convex drawings, in particular
Schnyder's and the recent Zhang and He bound for triangulations and the Chrobak and Kant bound for 3-connected planar graphs.
The algorithm takes linear time. The drawing algorithm has been implemented and tested. The expected grid size for the drawing
of a random triangulation is close to
For a random 3-connected plane graph, tests show that the expected size of the drawing is
|
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|