Thông tin tài liệu
Nhan đề : | Inserting One Edge into a Simple Drawing is Hard |
Tác giả : | Alan, Arroyo Fabian, Klute Irene, Parada |
Năm xuất bản : | 2022 |
Nhà xuất bản : | Springer |
Tóm tắt : | A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear opseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. |
Mô tả: | CC BY |
URI: | https://link.springer.com/article/10.1007/s00454-022-00394-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7430 |
Bộ sưu tập | OER - Khoa học Tự nhiên |
XEM MÔ TẢ
45
XEM TOÀN VĂN
8
Danh sách tệp tin đính kèm: