Drawing planar graphs using the lmc-ordering
- 1 January 1992
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 101-110
- https://doi.org/10.1109/sfcs.1992.267814
Abstract
The author introduces a method to optimize the required area, minimum angle and number of bends of planar drawings of graphs on a grid. The main tool is a new type of ordering on the vertices and faces of triconnected planar graphs. With this method linear time and space algorithms can be designed for many graph drawing problems. He shows that every triconnected planar graph G can be drawn convexly with straight lines on an (2n-4)*(n-2) grid. If G has maximum degree four (three), then G can be drawn orthogonal with at most (/sup 3n///sub 2/)+3 (at most (/sup n///sub 2/)+1) bends on an n*n grid ((/sup n///sub 2/)*(/sup n///sub 2/) grid, respectively). If G has maximum degree d, then G can be drawn planar on an (2n-6)*(3n-6) grid with minimum angle larger than /sup 1///sub d-2/ radians and at most 5n-15 bends. These results give in some cases considerable improvements over previous results, and give new bounds in other cases. Several other results, e.g. concerning visibility representations, are included.Keywords
This publication has 20 references indexed in Scilit:
- Planar graph augmentation problemsPublished by Springer Nature ,2005
- Hexagonal grid drawingsPublished by Springer Nature ,1993
- Constructing compact rectiliner planar layouts using canonical representation of planar graphsTheoretical Computer Science, 1992
- On the angular resolution of planar graphsPublished by Association for Computing Machinery (ACM) ,1992
- Triangulating planar graphs while minimizing the maximum degreePublished by Springer Nature ,1992
- Lower bounds for planar orthogonal drawings of graphsInformation Processing Letters, 1991
- Planar embedding: linear-time algorithms for vertex placement and edge orderingsIEEE Transactions on Circuits and Systems, 1988
- Planarity and duality of finite and infinite graphsJournal of Combinatorial Theory, Series B, 1980
- Dividing a Graph into Triconnected ComponentsSIAM Journal on Computing, 1973
- How to Draw a GraphProceedings of the London Mathematical Society, 1963