Convex drawing
In graph drawing, a convex drawing of a planar graph is a drawing that represents the vertices of the graph as points in the Euclidean plane and the edges as straight line segments, in such a way that all of the faces of the drawing (including the outer face) have a convex boundary. The boundary of a face may pass straight through one of the vertices of the graph without turning; a strictly convex drawing asks in addition that the face boundary turns at each vertex. That is, in a strictly convex drawing, each vertex of the graph is also a vertex of each convex polygon describing the shape of each incident face.
Every polyhedral graph has a strictly convex drawing,[1] for instance obtained as the Schlegel diagram of a convex polyhedron representing the graph. For these graphs, a convex (but not necessarily strictly convex) drawing can be found within a grid whose length on each side is linear in the number of vertices of the graph, in linear time.[2] However, strictly convex drawings may require larger grids; for instance, for any polyhedron such as a pyramid in which one face has a linear number of vertices, a strictly convex drawing of its graph requires a grid of cubic area.[3] A linear-time algorithm can find strictly convex drawings of polyhedral graphs in a grid whose length on each side is quadratic.[4]
Other graphs that are not polyhedral can also have convex drawings, or strictly convex drawings. A combinatorial characterization for the graphs with convex drawings is known,[5] and they can be recognized in linear time,[6] but the grid dimensions needed for their drawings and an efficient algorithm for constructing small convex grid drawings of these graphs are not known in all cases.[7]
References
- ^ Tutte, W. T. (1960), "Convex representations of graphs", Proceedings of the London Mathematical Society, Third Series, 10: 304–320, doi:10.1112/plms/s3-10.1.304, MR 0114774
- ^ Kant, G. (1996), "Drawing planar graphs using the canonical ordering", Algorithmica, 16 (1): 4–32, doi:10.1007/s004539900035, MR 1394492
- ^ Andrews, George E. (1963), "A lower bound for the volume of strictly convex bodies with many boundary lattice points", Transactions of the American Mathematical Society, 106: 270–279, doi:10.2307/1993769, MR 0143105
- ^ Bárány, Imre; Rote, Günter (2006), "Strictly convex drawings of planar graphs", Documenta Mathematica, 11: 369–391, arXiv:cs/0507030, MR 2262937
- ^ Thomassen, Carsten (1980), "Planarity and duality of finite and infinite graphs", Journal of Combinatorial Theory, Series B, 29 (2): 244–271, doi:10.1016/0095-8956(80)90083-0, MR 0586436
- ^ Chiba, Norishige; Yamanouchi, Tadashi; Nishizeki, Takao (1984), "Linear algorithms for convex drawings of planar graphs", in Bondy, J. Adrian; Murty, U. S. R. (eds.), Progress in graph theory (Waterloo, Ont., 1982), Academic Press, pp. 153–173, MR 0776799
- ^ Zhou, Xiao; Nishizeki, Takao (2010), "Convex drawings of internally triconnected plane graphs on grids", Discrete Mathematics, Algorithms and Applications, 2 (3): 347–362, doi:10.1142/S179383091000070X, MR 2728831
