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][3] 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.[4] A linear-time algorithm can find strictly convex drawings of polyhedral graphs in a grid whose length on each side is quadratic.[5]
Other graphs that are not polyhedral can also have convex drawings, or strictly convex drawings. Some graphs, such as the complete bipartite graph , have convex drawings but not strictly convex drawings. A combinatorial characterization for the graphs with convex drawings is known,[6] and they can be recognized in linear time,[7] 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.[8]
Convex drawings should be distinguished from convex embeddings, in which each vertex is required to lie within the convex hull of its neighboring vertices. Convex embeddings can exist in dimensions other than two, do not require their graph to be planar, and even for planar embeddings of planar graphs do not necessarily force the outer face to be convex.[9]
References
edit- ^ 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, hdl:1874/16676, MR 1394492
- ^ Bonichon, Nicolas; Felsner, Stefan; Mosbah, Mohamed (2007), "Convex drawings of 3-connected plane graphs", Algorithmica, 47 (4): 399–420, doi:10.1007/s00453-006-0177-6, MR 2304987, S2CID 375595
- ^ 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 (2): 270–279, doi:10.2307/1993769, JSTOR 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, doi:10.4171/dm/214, MR 2262937, S2CID 47071207
- ^ 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
- ^ Linial, N.; Lovász, L.; Wigderson, A. (1988), "Rubber bands, convex embeddings and graph connectivity", Combinatorica, 8 (1): 91–102, doi:10.1007/BF02122557, MR 0951998, S2CID 6164458
