@unpublished{6313,
abstract = {We prove three principal results. First we exhibit a drawing of $K_{10}$ in the plane for which there do not exist extensions of the edges to simple closed curves with any two curves intersecting at most twice. Second, we exhibit a drawing of $K_9$ that has an extension of its edges to simple closed curves such that any two curves intersect in at most two points, but no extension to simple closed curves has every two curves intersecting in exactly two points. Third, we show that every h-convex drawing (introduced by Arroyo et al, submitted) has extensions of its edges to simple closed curves such that any two curves intersect in exactly two points. Using this result, we show that} a set of three axioms of simple closed curve extensions characterizes h-convexity.},
author = {Arroyo Guevara, Alan M and Richter, Bruce and Sunohara, Matthew},
pages = {35},
title = {{Extending drawings of complete graphs into arrangements of pseudocircles}},
year = {2019},
}
@inproceedings{7230,
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.},
author = {Arroyo Guevara, Alan M and Derka, Martin and Parada, Irene},
booktitle = {Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)},
isbn = {9783030358013},
issn = {16113349},
location = {Prague, Czech Republic},
pages = {230--243},
publisher = {Springer Nature},
title = {{Extending simple drawings}},
doi = {10.1007/978-3-030-35802-0_18},
volume = {11904},
year = {2019},
}
@article{6638,
abstract = {The crossing number of a graph G is the least number of crossings over all possible drawings of G. We present a structural characterization of graphs with crossing number one.},
author = {Silva, André and Arroyo Guevara, Alan M and Richter, Bruce and Lee, Orlando},
issn = {0012-365X},
journal = {Discrete Mathematics},
number = {11},
pages = {3201--3207},
publisher = {Elsevier},
title = {{Graphs with at most one crossing}},
doi = {10.1016/j.disc.2019.06.031},
volume = {342},
year = {2019},
}