Extending simple drawings

A.M. Arroyo Guevara, M. Derka, I. Parada, in:, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Nature, 2019, pp. 230–243.


Conference Paper | Published | English

Scopus indexed
Author
Arroyo Guevara, Alan MIST Austria; Derka, Martin; Parada, Irene
Department
Series Title
LNCS
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.
Publishing Year
Date Published
2019-11-28
Proceedings Title
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume
11904
Page
230-243
Conference
GD: Graph Drawing and Network Visualization
Conference Location
Prague, Czech Republic
Conference Date
2019-09-17 – 2019-09-20
ISSN
eISSN
IST-REx-ID

Cite this

Arroyo Guevara AM, Derka M, Parada I. Extending simple drawings. In: Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 11904. Springer Nature; 2019:230-243. doi:10.1007/978-3-030-35802-0_18
Arroyo Guevara, A. M., Derka, M., & Parada, I. (2019). Extending simple drawings. In Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. https://doi.org/10.1007/978-3-030-35802-0_18
Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple Drawings.” In Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 11904:230–43. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-35802-0_18.
A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,” in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Prague, Czech Republic, 2019, vol. 11904, pp. 230–243.
Arroyo Guevara AM, Derka M, Parada I. 2019. Extending simple drawings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). GD: Graph Drawing and Network Visualization, LNCS, vol. 11904. 230–243.
Arroyo Guevara, Alan M., et al. “Extending Simple Drawings.” Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11904, Springer Nature, 2019, pp. 230–43, doi:10.1007/978-3-030-35802-0_18.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]

Link(s) to Main File(s)
Access Level
OA Open Access

Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1908.08129

Search this title in

Google Scholar
ISBN Search