Trong lý thuyết đồ thị, chiều dày của một đồ thị G là số đồ thị phẳng tối thiểu mà trong đó các cạnh của G có thể được phân chia. Nghĩa là, nếu tồn tại một tập hợp các đồ thị phẳng phẳng, tất cả đều có cùng một tập các đỉnh, như vậy sự kết hợp của những đồ thị phẳng này là G, sau đó độ dày của G là tối đa k Nói cách khác, chiều dày của một đồ thị là số lượng nhỏ nhất các đồ thị con phẳng có công thức tương đương với đồ thị G.
Như vậy, một đồ thị phẳng có độ dày 1. Đồ thị của độ dày 2 được gọi là đồ thị biplanar. Khái niệm độ dày bắt nguồn từ giả thuyết năm 1962 của Frank Harary: Đối với bất kỳ biểu đồ nào trên 9 điểm, bản thân nó hoặc biểu đồ bổ sung của nó là không phẳng. Vấn đề là tương đương với việc xác định xem đồ thị K9 có đầy đủ là biplanar hay không và phỏng đoán là đúng.Một cuộc khảo sát toàn diện về nghệ thuật của chủ đề như năm 1998 được viết bởi Petra Mutzel, Thomas Odenthal và Mark Scharbrodt.
Các đồ thị cụ thể
Độ dày của đồ thị đầy đủ trên n đỉnh, Kn, là
Với một số trường hợp ngoại lệ, độ dày của một đồ thị hoàn toàn hai bên Ka, b nói chung là:
Các vấn đề liên quan
Mỗi khu rừng đều phẳng, và mỗi đồ thị có thể chia thành tối đa ba khu rừng. Do đó, chiều dày của bất kỳ đồ thị G nào cũng bằng arboricity của cùng một biểu đồ (số lượng rừng tối thiểu có thể được phân chia) và ít nhất bằng ba phần chia cho ba. Độ dày của G cũng nằm trong các yếu tố không đổi của một biến thể đồ thị tiêu chuẩn khác, sự thoái hoá, được định nghĩa là lớn nhất, trên đồ thị con của G, mức độ tối thiểu trong đồ thị con. Nếu một biểu đồ n-đỉnh có độ dày t thì nó nhất thiết phải có nhiều cạnh t (3n – 6), từ đó nó suy thoái của nó là nhiều nhất là 6t – 1. Theo hướng khác, nếu một đồ thị bị suy thoái D thì nó có độ mỡ, độ dày, tối đa D.
Độ dày liên quan chặt chẽ đến vấn đề nhúng đồng thời. Nếu hai hoặc nhiều đồ thị phẳng đều chia sẻ cùng một đỉnh, thì có thể nhúng tất cả các đồ thị này vào mặt phẳng, với các cạnh vẽ theo đường cong, sao cho mỗi đỉnh có cùng vị trí trong tất cả các bản vẽ khác nhau. Tuy nhiên, có thể không thể xây dựng một bản vẽ như vậy trong khi vẫn giữ các cạnh vẽ như các đoạn thẳng.
Một đồ thị khác bất biến, bề dày tĩnh hoặc độ dày hình học của một đồ thị G, tính số đồ thị phẳng nhất mà G có thể bị phân hủy theo giới hạn mà tất cả các đồ thị có thể được vẽ đồng thời với các cạnh thẳng. Độ dày của sách cho biết thêm một hạn chế bổ sung, rằng tất cả các đỉnh được vẽ ở vị trí lồi, tạo thành một bố cục tròn của đồ thị. Tuy nhiên, trái ngược với tình huống của sự mờ và suy thoái, không có hai trong số ba tham số độ dày này luôn nằm trong một yếu tố liên tục của nhau.
Tính toán phức tạp
Nó là NP-hard để tính độ dày của một đồ thị, và NP-complete để kiểm tra xem độ dày tối đa là hai hay không. Tuy nhiên, kết nối với arboricity cho phép độ dày được ước lượng trong một tỷ lệ xấp xỉ 3 trong thời gian đa thức.