Inserting One Edge into a Simple Drawing is Hard
CC BY
Lưu vào:
| Tác giả chính: | , , |
|---|---|
| Định dạng: | Sách |
| Ngôn ngữ: | English |
| Nhà xuất bản: |
Springer
2023
|
| Chủ đề: | |
| Truy cập trực tuyến: | https://link.springer.com/article/10.1007/s00454-022-00394-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7430 |
| Từ khóa: |
Thêm từ khóa
Không có từ khóa, Hãy là người đầu tiên đánh dấu biểu ghi này!
|
| id |
oai:localhost:PNK-7430 |
|---|---|
| record_format |
dspace |
| spelling |
oai:localhost:PNK-74302023-04-03T04:53:15Z Inserting One Edge into a Simple Drawing is Hard Alan, Arroyo Fabian, Klute Irene, Parada D(G) of a graph G G+e extending D(G) CC BY 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. 2023-04-03T04:53:15Z 2023-04-03T04:53:15Z 2022 Book https://link.springer.com/article/10.1007/s00454-022-00394-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7430 en application/pdf Springer |
| institution |
Digital Phenikaa |
| collection |
Digital Phenikaa |
| language |
English |
| topic |
D(G) of a graph G G+e extending D(G) |
| spellingShingle |
D(G) of a graph G G+e extending D(G) Alan, Arroyo Fabian, Klute Irene, Parada Inserting One Edge into a Simple Drawing is Hard |
| description |
CC BY |
| format |
Book |
| author |
Alan, Arroyo Fabian, Klute Irene, Parada |
| author_facet |
Alan, Arroyo Fabian, Klute Irene, Parada |
| author_sort |
Alan, Arroyo |
| title |
Inserting One Edge into a Simple Drawing is Hard |
| title_short |
Inserting One Edge into a Simple Drawing is Hard |
| title_full |
Inserting One Edge into a Simple Drawing is Hard |
| title_fullStr |
Inserting One Edge into a Simple Drawing is Hard |
| title_full_unstemmed |
Inserting One Edge into a Simple Drawing is Hard |
| title_sort |
inserting one edge into a simple drawing is hard |
| publisher |
Springer |
| publishDate |
2023 |
| url |
https://link.springer.com/article/10.1007/s00454-022-00394-9 https://dlib.phenikaa-uni.edu.vn/handle/PNK/7430 |
| _version_ |
1762184303077228544 |
| score |
8.893527 |