Cover Image

Inserting One Edge into a Simple Drawing is Hard

CC BY

Saved in:
Bibliographic Details
Main Authors: Alan, Arroyo, Fabian, Klute, Irene, Parada
Format: Book
Language:English
Published: Springer 2023
Subjects:
D(G) of a graph G
G+e extending D(G)
Online Access:https://link.springer.com/article/10.1007/s00454-022-00394-9
https://dlib.phenikaa-uni.edu.vn/handle/PNK/7430
Tags: Add Tag
No Tags, Be the first to tag this record!
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.891787

Similar Items