---
res:
bibo_abstract:
- Simple drawings of graphs are those in which each pair of edges share at most
one point, either a common endpoint or a proper crossing. In this paper we study
the problem of extending a simple drawing D(G) of a graph G by inserting a set
of edges from the complement of G into D(G) such that the result is a simple drawing.
In the context of rectilinear drawings, the problem is trivial. For pseudolinear
drawings, the existence of such an extension follows from Levi’s enlargement lemma.
In contrast, we prove that deciding if a given set of edges can be inserted into
a simple drawing is NP-complete. Moreover, we show that the maximization version
of the problem is APX-hard. We also present a polynomial-time algorithm for deciding
whether one edge uv can be inserted into D(G) when {u,v} is a dominating set for
the graph G.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Alan M
foaf_name: Arroyo Guevara, Alan M
foaf_surname: Arroyo Guevara
foaf_workInfoHomepage: http://www.librecat.org/personId=3207FDC6-F248-11E8-B48F-1D18A9856A87
- foaf_Person:
foaf_givenName: Martin
foaf_name: Derka, Martin
foaf_surname: Derka
- foaf_Person:
foaf_givenName: Irene
foaf_name: Parada, Irene
foaf_surname: Parada
bibo_doi: 10.1007/978-3-030-35802-0_18
bibo_volume: 11904
dct_date: 2019^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/03029743
- http://id.crossref.org/issn/16113349
- http://id.crossref.org/issn/9783030358013
dct_language: eng
dct_publisher: Springer Nature@
dct_title: Extending simple drawings@
...