---
_id: '7230'
abstract:
- lang: eng
  text: 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.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Alan M
  full_name: Arroyo Guevara, Alan M
  id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
  last_name: Arroyo Guevara
  orcid: 0000-0003-2401-8670
- first_name: Martin
  full_name: Derka, Martin
  last_name: Derka
- first_name: Irene
  full_name: Parada, Irene
  last_name: Parada
citation:
  ama: 'Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: <i>27th
    International Symposium on Graph Drawing and Network Visualization</i>. Vol 11904.
    Springer Nature; 2019:230-243. doi:<a href="https://doi.org/10.1007/978-3-030-35802-0_18">10.1007/978-3-030-35802-0_18</a>'
  apa: 'Arroyo Guevara, A. M., Derka, M., &#38; Parada, I. (2019). Extending simple
    drawings. In <i>27th International Symposium on Graph Drawing and Network Visualization</i>
    (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-35802-0_18">https://doi.org/10.1007/978-3-030-35802-0_18</a>'
  chicago: Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple
    Drawings.” In <i>27th International Symposium on Graph Drawing and Network Visualization</i>,
    11904:230–43. Springer Nature, 2019. <a href="https://doi.org/10.1007/978-3-030-35802-0_18">https://doi.org/10.1007/978-3-030-35802-0_18</a>.
  ieee: A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,”
    in <i>27th International Symposium on Graph Drawing and Network Visualization</i>,
    Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.
  ista: 'Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. 27th
    International Symposium on Graph Drawing and Network Visualization. GD: Graph
    Drawing and Network Visualization, LNCS, vol. 11904, 230–243.'
  mla: Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” <i>27th International
    Symposium on Graph Drawing and Network Visualization</i>, vol. 11904, Springer
    Nature, 2019, pp. 230–43, doi:<a href="https://doi.org/10.1007/978-3-030-35802-0_18">10.1007/978-3-030-35802-0_18</a>.
  short: A.M. Arroyo Guevara, M. Derka, I. Parada, in:, 27th International Symposium
    on Graph Drawing and Network Visualization, Springer Nature, 2019, pp. 230–243.
conference:
  end_date: 2019-09-20
  location: Prague, Czech Republic
  name: 'GD: Graph Drawing and Network Visualization'
  start_date: 2019-09-17
date_created: 2020-01-05T23:00:47Z
date_published: 2019-11-28T00:00:00Z
date_updated: 2023-09-06T14:56:00Z
day: '28'
department:
- _id: UlWa
doi: 10.1007/978-3-030-35802-0_18
ec_funded: 1
external_id:
  arxiv:
  - '1908.08129'
  isi:
  - '000612918800018'
intvolume: '     11904'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1908.08129
month: '11'
oa: 1
oa_version: Preprint
page: 230-243
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: 27th International Symposium on Graph Drawing and Network Visualization
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - 978-3-0303-5801-3
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending simple drawings
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11904
year: '2019'
...