---
_id: '8732'
abstract:
- lang: eng
  text: '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 (pseudolinear), 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. On the positive side, we show that, given an arrangement of
    pseudocircles   A  and a pseudosegment   σ , it can be decided in polynomial time
    whether there exists a pseudocircle   Φσ  extending   σ  for which   A∪{Φσ}  is
    again an arrangement of pseudocircles.'
alternative_title:
- LNCS
article_processing_charge: No
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: Fabian
  full_name: Klute, Fabian
  last_name: Klute
- first_name: Irene
  full_name: Parada, Irene
  last_name: Parada
- first_name: Raimund
  full_name: Seidel, Raimund
  last_name: Seidel
- first_name: Birgit
  full_name: Vogtenhuber, Birgit
  last_name: Vogtenhuber
- first_name: Tilo
  full_name: Wiedera, Tilo
  last_name: Wiedera
citation:
  ama: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
    Inserting one edge into a simple drawing is hard. In: <i>Graph-Theoretic Concepts
    in Computer Science</i>. Vol 12301. Springer Nature; 2020:325-338. doi:<a href="https://doi.org/10.1007/978-3-030-60440-0_26">10.1007/978-3-030-60440-0_26</a>'
  apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
    &#38; Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
    <i>Graph-Theoretic Concepts in Computer Science</i> (Vol. 12301, pp. 325–338).
    Leeds, United Kingdom: Springer Nature. <a href="https://doi.org/10.1007/978-3-030-60440-0_26">https://doi.org/10.1007/978-3-030-60440-0_26</a>'
  chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Raimund Seidel, Birgit
    Vogtenhuber, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.”
    In <i>Graph-Theoretic Concepts in Computer Science</i>, 12301:325–38. Springer
    Nature, 2020. <a href="https://doi.org/10.1007/978-3-030-60440-0_26">https://doi.org/10.1007/978-3-030-60440-0_26</a>.
  ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, and
    T. Wiedera, “Inserting one edge into a simple drawing is hard,” in <i>Graph-Theoretic
    Concepts in Computer Science</i>, Leeds, United Kingdom, 2020, vol. 12301, pp.
    325–338.
  ista: 'Arroyo Guevara AM, Klute F, Parada I, Seidel R, Vogtenhuber B, Wiedera T.
    2020. Inserting one edge into a simple drawing is hard. Graph-Theoretic Concepts
    in Computer Science. WG: Workshop on Graph-Theoretic Concepts in Computer Science,
    LNCS, vol. 12301, 325–338.'
  mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
    Hard.” <i>Graph-Theoretic Concepts in Computer Science</i>, vol. 12301, Springer
    Nature, 2020, pp. 325–38, doi:<a href="https://doi.org/10.1007/978-3-030-60440-0_26">10.1007/978-3-030-60440-0_26</a>.
  short: A.M. Arroyo Guevara, F. Klute, I. Parada, R. Seidel, B. Vogtenhuber, T. Wiedera,
    in:, Graph-Theoretic Concepts in Computer Science, Springer Nature, 2020, pp.
    325–338.
conference:
  end_date: 2020-06-26
  location: Leeds, United Kingdom
  name: 'WG: Workshop on Graph-Theoretic Concepts in Computer Science'
  start_date: 2020-06-24
date_created: 2020-11-06T08:45:03Z
date_published: 2020-10-09T00:00:00Z
date_updated: 2023-09-05T15:09:16Z
day: '09'
department:
- _id: UlWa
doi: 10.1007/978-3-030-60440-0_26
ec_funded: 1
intvolume: '     12301'
language:
- iso: eng
month: '10'
oa_version: None
page: 325-338
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '754411'
  name: ISTplus - Postdoctoral Fellowships
publication: Graph-Theoretic Concepts in Computer Science
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783030604394'
  - '9783030604400'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inserting one edge into a simple drawing is hard
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12301
year: '2020'
...