볼록도

같은 그래프의 볼록하고 엄밀하게 볼록한 격자 도면

그래프 그리기에서 평면 그래프의 볼록한 그림은 그래프의 정점을 유클리드 평면에서 점으로, 모서리를 직선 세그먼트로 나타내는 그림으로, 그림의 모든 면(외면 포함)이 볼록한 경계를 가지도록 합니다.면의 경계는 회전하지 않고 그래프의 정점 중 하나를 똑바로 통과할 수 있습니다. 엄밀하게 볼록한 도면은 면 경계가 각 정점에서 회전하도록 추가로 요구합니다.즉, 엄밀하게 볼록한 그림에서 그래프의 각 정점은 각 입사면의 모양을 설명하는 각 볼록 다각형의 정점이기도 합니다.

모든 다면체 그래프는 엄밀하게 볼록한 ^[1]그림을 가지고 있으며, 예를 들어 그래프를 나타내는 볼록한 다면체의 슐레겔 다이어그램으로 얻을 수 있다.이러한 그래프의 경우, 각 면의 길이가 그래프의 정점 수에서 선형인 그리드 내에서 볼록한(단, 엄밀하게 볼록한 것은 아님) 도면을 선형 ^[2]^[3]시간으로 찾을 수 있다.그러나 엄밀하게 볼록한 도면은 더 큰 격자를 필요로 할 수 있습니다. 예를 들어, 한 면에 선형적인 수의 정점이 있는 피라미드와 같은 다면체의 경우, 그래프의 엄밀하게 볼록한 도면은 입방체 ^[4]면적의 격자를 필요로 합니다.선형 시간 알고리즘은 각 변의 길이가 ^[5]2차인 그리드에서 다면체 그래프의 엄밀하게 볼록한 도면을 찾을 수 있다.

완전

한 초당

K_{2,3}

K_{2,3}

2,

K_{2,3}

3(표시 스타일 K_

{2,

3})의 볼록하지만 엄밀하게 볼록하지는 않은 도면

다면체가 아닌 다른 그래프도 볼록한 도면 또는 엄밀하게 볼록한 도면을 가질 수 있습니다.완전 이분 $K_{2,3}$ $K_{2,3}$ $(\$ 과 같은 일부 그래프는 볼록한 도면을 가지고 있지만 엄밀하게 볼록한 도면은 아니다.볼록한 도면을 가진 그래프에 대한 조합적 특성은 ^[6]알려져 있으며 선형 시간 ^[7]내에 인식할 수 있지만, 이들 도면에 필요한 그리드 치수와 이들 그래프의 작은 볼록한 그리드 도면을 구축하기 위한 효율적인 알고리즘은 모든 ^[8]경우에 알려져 있지 않다.

볼록 도면은 각 정점이 인접 정점의 볼록 선체 내에 있어야 하는 볼록 매립물과 구별되어야 한다.볼록 임베딩은 2가 아닌 차원으로 존재할 수 있으며, 그래프가 평면일 필요는 없으며, 평면 그래프의 평면 임베딩에 대해서도 외부 면이 ^[9]볼록할 필요는 없다.

레퍼런스

^ 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, 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 $O(n^{2})$ 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

[tutte-1] 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-2] Kant, G. (1996), "Drawing planar graphs using the canonical ordering", Algorithmica, 16 (1): 4–32, doi:10.1007/s004539900035, hdl:1874/16676, MR 1394492

[bfm-3] 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-4] 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

[br-5] 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-6] 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

[cyn-7] 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

[zn-8] Zhou, Xiao; Nishizeki, Takao (2010), "Convex drawings of internally triconnected plane graphs on $O(n^{2})$ grids", Discrete Mathematics, Algorithms and Applications, 2 (3): 347–362, doi:10.1142/S179383091000070X, MR 2728831

[llw-9] 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

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

볼록도

네임스페이스

더

레퍼런스