박스시티

사각형 교차 그래프(박스성 2 포함)

그래프 이론에서 박스성은 1969년에 Fred S. Roberts에 의해 소개된 그래프 불변성이다.

그래프의 박스성은 주어진 그래프를 축-병렬 상자의 교차 그래프로 나타낼 수 있는 최소 치수다.즉, 해당 정점을 연결하는 가장자리가 있는 경우에만 두 상자가 교차하도록 그래프의 정점과 상자 세트 사이에 일대일 일치성이 있어야 한다.

예

그림은 정점이 6개인 그래프를 보여주고, 직사각형의 교차 그래프(2차원 상자)로 이 그래프를 나타낸다.이 그래프는 더 낮은 차원에 있는 박스의 교차 그래프로 나타낼 수 없으므로 박스성은 2이다.

로버츠(1969)는 2n 정점의 완전한 그래프에서 완벽한 일치를 제거함으로써 형성된 2n 정점을 가진 그래프는 정확히 박스성을 가지고 있다는 것을 보여주었다. 각각의 정점 쌍은 서로 다른 차원으로 분리된 상자로 표시되어야 한다.n차원 하이퍼큐브의 2n 면을 각각 박스로 두껍게 만들어 이 그래프의 상자 표상을 정확히 n 치수가 n인 것으로 볼 수 있다.이러한 결과 때문에 이 그래프는 칵테일 파티 그래프로 더 잘 알려져 있고 투란 그래프 T(2n,n)로도 이해할 수 있지만 로버츠 그래프라고 불려왔다.^[1]

다른 그래프 클래스와의 관계

그래프는 구간 그래프인 경우에만 박스성을 가진다. 임의 그래프 G의 박스성은 구간 그래프의 에지 집합의 교차점이 G가 되도록 동일한 정점 집합에 있는 구간 그래프의 최소 개수를 의미한다.모든 외부 평면 그래프는 최대 2개의 박스성을 가지며,^[2] 모든 평면 그래프는 최대 3개의 박스성을 가진다.^[3]

초당적 그래프가 상자성 2를 갖는 경우 평면에서 축 평행선 세그먼트의 교차 그래프로 나타낼 수 있다.^[4]

Adiga, Bhowmick &, Chandran(2011년):최소 구성 요소의 집합 G, 최대 요소의 집합 G의 두번째partite가 지고 두 elem에 해당합니다의 한partite 집단에 상응한 것은 양분 그래프 G의 boxicity은 height-two의 순서 측면 부분적으로 순서의 인자 2G로 연결된 세트 이내에 있다는 것을 증명했다.ents해당 정점이 G에 인접할 경우 비교 가능하다. 동등하게, 높이 2의 부분 순서가 지정된 P의 순서 치수는 P의 비교가능성 그래프의 상자성(P가 높이가 2이므로 양분)의 요인 2 내에 있다.

알고리즘 결과

많은 그래프 문제는 다른 그래프보다 경계 상자성이 있는 그래프의 경우 더 효율적으로 해결되거나 근사치가 가능하다. 예를 들어, 경계 상자성이 있는 그래프의 경우 최대 집단 문제는 다항 시간 내에 해결할 수 있다.^[5]일부 다른 그래프 문제의 경우 저차원 상자 표현이 알려진 경우 효율적인 솔루션 또는 근사치를 찾을 수 있다.^[6]그러나 이러한 표현을 발견 그것은 NP-완전 지정된 그래프의 boxicity 있는지 시험해 보기 어려울 것에 대부분 어떤 일정한 가치 K, 심지어 K=2.[7]Chandran, 프랜시스 &,Sivadasan(2010년)를 설명하는 알고리즘을 찾고 표현 방법의 임의의 그래프로 교차 그래프의 상자, 크기 범위 내에서 거리를 통나무.arithm그래프의 최대 수준의 IC 인자. 이 결과는 그래프의 상자성에 상한을 제공한다.

박시성은 자연 파라미터가 어렵지만 입력 그래프의 꼭지점 커버 번호로 파라미터화할 때 고정 파라미터를 추적할 수 있다.^[8]

경계

그래프 G 그래프에 가장자리가 m이면: $box(G)=O({\sqrt {m\cdot \log(m)}})$ $box(G)=O({\sqrt {m\cdot \log(m)}})$ x $box(G)=O({\sqrt {m\cdot \log(m)}})$ ( G $box(G)=O({\sqrt {m\cdot \log(m)}})$ ) $box(G)=O({\sqrt {m\cdot \log(m)}})$ = $box(G)=O({\sqrt {m\cdot \log(m)}})$ ( $box(G)=O({\sqrt {m\cdot \log(m)}})$ ⁡ $box(G)=O({\sqrt {m\cdot \log(m)}})$ ( $box(G)=O({\sqrt {m\cdot \log(m)}})$ ) ${\displaystyle box(G)=O({\sqrt$ { $m\cdot \cdlog(m$ ^[9]^[10]

그래프 G가 k-degenerate( $k\geq 2$ $k\geq 2$ $k\geq 2$ ${\displaystyle$ k $\geq$ 2} $k\geq 2$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $k\geq 2$ 이고 정점이 n이면, G는 상자성 $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ x $box(G)\leq (k+2)\lceil 2e\log n\rceil$ ( $box(G)\leq (k+2)\lceil 2e\log n\rceil$ ) $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ k $box(G)\leq (k+2)\lceil 2e\log n\rceil$ + $box(G)\leq (k+2)\lceil 2e\log n\rceil$ ) $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ { $box(G)\leq (k+2)\lceil 2e\log n\rceil$ { { { { { $\displaystystystylebox(G)\leq$ ( $k)\n\rceil$ $box(G)\leq (k+2)\lceil 2e\log n\rceil$ ^[11]

만약 그래프 G는 미성년으로 tvertices에 대한 완전 그래프고 있지만 있지 vertices에서 작은 없어 완전 그래프, 그리고 boxicity Ω과 그래프(t로그 ⁡어){\displaystyle \Omega(t{\sqrt{\log t}})}특히 .[13], 어떤 그래프 Ghax.,)O{\displaystyle box(G)=O(t^{2}\log지)}[12](t2로그 ⁡ 금년)입니다 x(G)largeenough이다oxicity $box(G)=O(\mu (G)^{2}\log \mu (G))$ $box(G)=O(\mu (G)^{2}\log \mu (G))$ ( $box(G)=O(\mu (G)^{2}\log \mu (G))$ ) $box(G)=O(\mu (G)^{2}\log \mu (G))$ = O $box(G)=O(\mu (G)^{2}\log \mu (G))$ ( $box(G)=O(\mu (G)^{2}\log \mu (G))$ ( $box(G)=O(\mu (G)^{2}\log \mu (G))$ ) 2 $box(G)=O(\mu (G)^{2}\log \mu (G))$ ( $box(G)=O(\mu (G)^{2}\log \mu (G))$ ) $box(G)=O(\mu (G)^{2}\log \mu (G))$ ) ${\displaystyle box(G)=O(\mu (G)^{2}\$ $log \mu (G$ $box(G)=O(\mu (G)^{2}\log \mu (G))$ 여기서 $($ )는 G의 콜린 드 베르디아레 불변성을 의미한다 $\mu (G)$ .

메모들

^ 예: 찬드란, 프랜시스 & 시바다산(2010) 및 찬드란 & 시바다산(2007)을 참조한다.
^ 스키너맨(1984년).
^ 토마센(1986년).
^ 벨란토니 외 연구진(1993)
^ 찬드란, 프랜시스 & 시바다산(2010)은 이 그래프들이 다항식 수의 최대 패거리들을 가지고 있다는 사실에서 이러한 결과가 나온다고 관찰한다.모든 최대 계층을 효율적으로 나열하기 위해 명시적인 박스 표현이 필요하지 않다.
^ 예: Agarwal, Van Kreveld & Suri(1998년) 및 Berman 등. (2001) 직사각형의 교차로 그래프에 대한 최대 독립 집합에 대한 근사치 및 높은 치수에서 이러한 문제의 근사치 경도에 대한 결과에 대한 Clebik & Chlebikova(2005)에 대한 근사치.
^ Cozens(1981)는 박스시티 계산이 NP-완전하다는 것을 보여주고, Yannakakis(1982)는 박스시티가 최대 3인지 확인하는 것조차 NP-하드라는 것을 보여주며, 마지막으로 Kratochvil(1994)은 박스시티 2를 인식하는 것이 NP-하드라는 것을 보여주었다.
^ 아디가, 치트니스 & 사우라브(2010년).
^ 찬드란, 프랜시스 & 시바다산(2010년)
^ 에스페레트 (2016)
^ 아디가, 찬드란 & 매튜 (2014년)
^ 에스페레 & 위쳇(2018)
^ 에스페레트 (2016)

참조

Adiga, Abhijin; Bhowmick, Diptendu; Chandran, L. Sunil (2011), "Boxicity and Poset Dimension", SIAM Journal on Discrete Mathematics, 25 (4): 1687–1698, arXiv:1003.2357, doi:10.1137/100786290.
Adiga, Abhijin; Chandran, L. Sunil; Mathew, Rogers (2014), "Cubicity, Degeneracy, and Crossing Number", European Journal of Combinatorics, 35: 2–12, arXiv:1105.5225, doi:10.1016/j.ejc.2013.06.021.
Adiga, Abhijin; Chitnis, Rajesh; Saurabh, Saket (2010), "Parameterized algorithms for boxicity", Algorithms and Computation: 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part I (PDF), Lecture Notes in Computer Science, vol. 6506, pp. 366–377, doi:10.1007/978-3-642-17517-6_33, archived from the original (PDF) on 2017-08-30, retrieved 2018-01-22
Agarwal, Pankaj K.; van Kreveld, Marc; Suri, Subhash (1998), "Label placement by maximum independent set in rectangles", Computational Geometry Theory and Applications, 11 (3–4): 209–218, doi:10.1016/S0925-7721(98)00028-5, hdl:1874/18908.
Bellantoni, Stephen J.; Ben-Arroyo Hartman, Irith; Przytycka, Teresa; Whitesides, Sue (1993), "Grid intersection graphs and boxicity", Discrete Mathematics, 114 (1–3): 41–49, doi:10.1016/0012-365X(93)90354-V.
Berman, Piotr; DasGupta, B.; Muthukrishnan, S.; Ramaswami, S. (2001), "Efficient approximation algorithms for tiling and packing problems with rectangles", J. Algorithms, 41 (2): 443–470, doi:10.1006/jagm.2001.1188.
Chandran, L. Sunil; Francis, Mathew C.; Sivadasan, Naveen (2010), "Geometric representation of graphs in low dimension using axis parallel boxes", Algorithmica, 56 (2): 129–140, arXiv:cs.DM/0605013, doi:10.1007/s00453-008-9163-5, MR 2576537, S2CID 17838951.
Chandran, L. Sunil; Sivadasan, Naveen (2007), "Boxicity and treewidth", Journal of Combinatorial Theory, Series B, 97 (5): 733–744, arXiv:math.CO/0505544, doi:10.1016/j.jctb.2006.12.004, S2CID 9854207.
Chlebík, Miroslav; Chlebíková, Janka (2005), "Approximation hardness of optimization problems in intersection graphs of d-dimensional boxes", Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 267–276.
Cozzens, M. B. (1981), Higher and Multidimensional Analogues of Interval Graphs, Ph.D. thesis, Rutgers University.
Esperet, Louis (2016), "Boxicity and topological invariants", European Journal of Combinatorics, 51: 495–499, arXiv:1503.05765, doi:10.1016/j.ejc.2015.07.020, S2CID 5548385.
Esperet, Louis; Wiechert, Veit (2018), "Boxicity, poset dimension, and excluded minors", Electronic Journal of Combinatorics, 25 (4): #P4.51, arXiv:1804.00850, doi:10.37236/7787, S2CID 119148637.
Kratochvil, Jan (1994), "A special planar satisfiability problem and a consequence of its NP–completeness", Discrete Applied Mathematics, 52 (3): 233–252, doi:10.1016/0166-218X(94)90143-0.
Quest, M.; Wegner, G. (1990), "Characterization of the graphs with boxicity ≤ 2", Discrete Mathematics, 81 (2): 187–192, doi:10.1016/0012-365X(90)90151-7.
Roberts, F. S. (1969), "On the boxicity and cubicity of a graph", in Tutte, W. T. (ed.), Recent Progress in Combinatorics, Academic Press, pp. 301–310, ISBN 978-0-12-705150-5.
Scheinerman, E. R. (1984), Intersection Classes and Multiple Intersection Parameters, Ph. D thesis, Princeton University.
Thomassen, Carsten (1986), "Interval representations of planar graphs", Journal of Combinatorial Theory, Series B, 40: 9–20, doi:10.1016/0095-8956(86)90061-4.
Yannakakis, Mihalis (1982), "The complexity of the partial order dimension problem", SIAM Journal on Algebraic and Discrete Methods, 3 (3): 351–358, doi:10.1137/0603036.

[1] 예: 찬드란, 프랜시스 & 시바다산(2010) 및 찬드란 & 시바다산(2007)을 참조한다.

[2] 스키너맨(1984년).

[3] 토마센(1986년).

[4] 벨란토니 외 연구진(1993)

[5] 찬드란, 프랜시스 & 시바다산(2010)은 이 그래프들이 다항식 수의 최대 패거리들을 가지고 있다는 사실에서 이러한 결과가 나온다고 관찰한다.모든 최대 계층을 효율적으로 나열하기 위해 명시적인 박스 표현이 필요하지 않다.

[6] 예: Agarwal, Van Kreveld & Suri(1998년) 및 Berman 등. (2001) 직사각형의 교차로 그래프에 대한 최대 독립 집합에 대한 근사치 및 높은 치수에서 이러한 문제의 근사치 경도에 대한 결과에 대한 Clebik & Chlebikova(2005)에 대한 근사치.

[7] Cozens(1981)는 박스시티 계산이 NP-완전하다는 것을 보여주고, Yannakakis(1982)는 박스시티가 최대 3인지 확인하는 것조차 NP-하드라는 것을 보여주며, 마지막으로 Kratochvil(1994)은 박스시티 2를 인식하는 것이 NP-하드라는 것을 보여주었다.

[8] 아디가, 치트니스 & 사우라브(2010년).

[9] 찬드란, 프랜시스 & 시바다산(2010년)

[10] 에스페레트 (2016)

[11] 아디가, 찬드란 & 매튜 (2014년)

[12] 에스페레 & 위쳇(2018)

[13] 에스페레트 (2016)

[1]

[2]

[3]

[4]

[5]

[6]

[8]

[9]

[10]

[11]

Search

박스시티

네임스페이스

더

목차

예

다른 그래프 클래스와의 관계

알고리즘 결과

경계

관련 그래프 불변성

메모들

참조