---
_id: '13969'
abstract:
- lang: eng
text: "Bundling crossings is a strategy which can enhance the readability\r\nof
graph drawings. In this paper we consider good drawings, i.e., we require that\r\nany
two edges have at most one common point which can be a common vertex or a\r\ncrossing.
Our main result is that there is a polynomial-time algorithm to compute an\r\n8-approximation
of the bundled crossing number of a good drawing with no toothed\r\nhole. In general
the number of toothed holes has to be added to the 8-approximation.\r\nIn the
special case of circular drawings the approximation factor is 8, this improves\r\nupon
the 10-approximation of Fink et al. [14]. Our approach also works with the same\r\napproximation
factor for families of pseudosegments, i.e., curves intersecting at most\r\nonce.
We also show how to compute a 9/2-approximation when the intersection graph of\r\nthe
pseudosegments is bipartite and has no toothed hole."
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
the workshop. The first author has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement
No 754411. The second author has been supported by the German Research Foundation
DFG Project FE 340/12-1. An extended abstract of this paper has been published in
the proceedings of WALCOM 2022 in the Springer LNCS series, vol. 13174, pages 383–395.
article_processing_charge: Yes
article_type: original
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: Stefan
full_name: Felsner, Stefan
last_name: Felsner
citation:
ama: Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. Journal
of Graph Algorithms and Applications. 2023;27(6):433-457. doi:10.7155/jgaa.00629
apa: Arroyo Guevara, A. M., & Felsner, S. (2023). Approximating the bundled
crossing number. Journal of Graph Algorithms and Applications. Brown University.
https://doi.org/10.7155/jgaa.00629
chicago: Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
Crossing Number.” Journal of Graph Algorithms and Applications. Brown University,
2023. https://doi.org/10.7155/jgaa.00629.
ieee: A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing number,”
Journal of Graph Algorithms and Applications, vol. 27, no. 6. Brown University,
pp. 433–457, 2023.
ista: Arroyo Guevara AM, Felsner S. 2023. Approximating the bundled crossing number.
Journal of Graph Algorithms and Applications. 27(6), 433–457.
mla: Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
Number.” Journal of Graph Algorithms and Applications, vol. 27, no. 6,
Brown University, 2023, pp. 433–57, doi:10.7155/jgaa.00629.
short: A.M. Arroyo Guevara, S. Felsner, Journal of Graph Algorithms and Applications
27 (2023) 433–457.
date_created: 2023-08-06T22:01:11Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.7155/jgaa.00629
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
file:
- access_level: open_access
checksum: 9c30d2b8e324cc1c904f2aeec92013a3
content_type: application/pdf
creator: dernst
date_created: 2023-08-07T08:00:48Z
date_updated: 2023-08-07T08:00:48Z
file_id: '13979'
file_name: 2023_JourGraphAlgorithms_Arroyo.pdf
file_size: 865774
relation: main_file
success: 1
file_date_updated: 2023-08-07T08:00:48Z
has_accepted_license: '1'
intvolume: ' 27'
issue: '6'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 433-457
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '11185'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Approximating the bundled crossing number
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2023'
...
---
_id: '11999'
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.'
acknowledgement: 'This work was started during the 6th Austrian–Japanese–Mexican–Spanish
Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants
for the good atmosphere as well as discussions on the topic. Also, we thank Jan
Kynčl for sending us remarks on a preliminary version of this work and an anonymous
referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie
grant agreement No 754411. Fabian Klute was partially supported by the Netherlands
Organisation for Scientific Research (NWO) under project no. 612.001.651 and by
the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were
partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was
also partially supported by the Independent Research Fund Denmark grant 2020-2023
(9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded
by the Ministry of Universities of Spain and the European Union (NextGenerationEU).
Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.'
article_processing_charge: Yes (in subscription journal)
article_type: original
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: Fabian
full_name: Klute, Fabian
last_name: Klute
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
- first_name: Raimund
full_name: Seidel, Raimund
last_name: Seidel
- first_name: Tilo
full_name: Wiedera, Tilo
last_name: Wiedera
citation:
ama: Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting
one edge into a simple drawing is hard. Discrete and Computational Geometry.
2023;69:745–770. doi:10.1007/s00454-022-00394-9
apa: Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R.,
& Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. Discrete
and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00394-9
chicago: Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber,
Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is
Hard.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00394-9.
ieee: A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and
T. Wiedera, “Inserting one edge into a simple drawing is hard,” Discrete and
Computational Geometry, vol. 69. Springer Nature, pp. 745–770, 2023.
ista: Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T.
2023. Inserting one edge into a simple drawing is hard. Discrete and Computational
Geometry. 69, 745–770.
mla: Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is
Hard.” Discrete and Computational Geometry, vol. 69, Springer Nature, 2023,
pp. 745–770, doi:10.1007/s00454-022-00394-9.
short: A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera,
Discrete and Computational Geometry 69 (2023) 745–770.
date_created: 2022-08-28T22:02:01Z
date_published: 2023-04-01T00:00:00Z
date_updated: 2023-08-14T12:51:25Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s00454-022-00394-9
ec_funded: 1
external_id:
arxiv:
- '1909.07347'
isi:
- '000840292800001'
file:
- access_level: open_access
checksum: def7ae3b28d9fd6aec16450e40090302
content_type: application/pdf
creator: alisjak
date_created: 2022-08-29T11:23:15Z
date_updated: 2022-08-29T11:23:15Z
file_id: '12006'
file_name: 2022_DiscreteandComputionalGeometry_Arroyo.pdf
file_size: 1002218
relation: main_file
success: 1
file_date_updated: 2022-08-29T11:23:15Z
has_accepted_license: '1'
intvolume: ' 69'
isi: 1
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
page: 745–770
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete and Computational Geometry
publication_identifier:
eissn:
- 1432-0444
issn:
- 0179-5376
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inserting one edge into a simple drawing is hard
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 69
year: '2023'
...
---
_id: '11185'
abstract:
- lang: eng
text: Bundling crossings is a strategy which can enhance the readability of graph
drawings. In this paper we consider bundlings for families of pseudosegments,
i.e., simple curves such that any two have share at most one point at which they
cross. Our main result is that there is a polynomial-time algorithm to compute
an 8-approximation of the bundled crossing number of such instances (up to adding
a term depending on the facial structure). This 8-approximation also holds for
bundlings of good drawings of graphs. In the special case of circular drawings
the approximation factor is 8 (no extra term), this improves upon the 10-approximation
of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection
graph of the pseudosegments is bipartite.
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
the workshop. The first author has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Sklodowska Curie grant agreement
No 754411. The second author has been supported by the German Research Foundation
DFG Project FE 340/12-1.
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: Stefan
full_name: Felsner, Stefan
last_name: Felsner
citation:
ama: 'Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In:
WALCOM 2022: Algorithms and Computation. Vol 13174. LNCS. Springer Nature;
2022:383-395. doi:10.1007/978-3-030-96731-4_31'
apa: 'Arroyo Guevara, A. M., & Felsner, S. (2022). Approximating the bundled
crossing number. In WALCOM 2022: Algorithms and Computation (Vol. 13174,
pp. 383–395). Jember, Indonesia: Springer Nature. https://doi.org/10.1007/978-3-030-96731-4_31'
chicago: 'Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
Crossing Number.” In WALCOM 2022: Algorithms and Computation, 13174:383–95.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-96731-4_31.'
ieee: 'A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing
number,” in WALCOM 2022: Algorithms and Computation, Jember, Indonesia,
2022, vol. 13174, pp. 383–395.'
ista: 'Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number.
WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS
vol. 13174, 383–395.'
mla: 'Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
Number.” WALCOM 2022: Algorithms and Computation, vol. 13174, Springer
Nature, 2022, pp. 383–95, doi:10.1007/978-3-030-96731-4_31.'
short: 'A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation,
Springer Nature, 2022, pp. 383–395.'
conference:
end_date: 2022-03-26
location: Jember, Indonesia
name: 'WALCOM: Algorithms and Computation'
start_date: 2022-03-24
date_created: 2022-04-17T22:01:47Z
date_published: 2022-03-16T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '16'
department:
- _id: UlWa
doi: 10.1007/978-3-030-96731-4_31
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
intvolume: ' 13174'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.14892'
month: '03'
oa: 1
oa_version: Preprint
page: 383-395
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'WALCOM 2022: Algorithms and Computation'
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030967307'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13969'
relation: later_version
status: public
scopus_import: '1'
series_title: LNCS
status: public
title: Approximating the bundled crossing number
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13174
year: '2022'
...
---
_id: '11938'
abstract:
- lang: eng
text: A matching is compatible to two or more labeled point sets of size n with
labels {1, . . . , n} if its straight-line drawing on each of these point sets
is crossing-free. We study the maximum number of edges in a matching compatible
to two or more labeled point sets in general position in the plane. We show that
for any two labeled sets of n points in convex position there exists a compatible
matching with ⌊√2n + 1 − 1⌋ edges. More generally, for any ℓ labeled point sets
we construct compatible matchings of size Ω(n1/ℓ). As a corresponding upper bound,
we use probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1))
edges. Finally, we show that Θ(log n) copies of any set of n points are necessary
and sufficient for the existence of labelings of these point sets such that any
compatible matching consists only of a single edge.
acknowledgement: 'A.A. funded by the Marie Sklodowska-Curie grant agreement No 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- 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: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
Journal of Graph Algorithms and Applications. 2022;26(2):225-240. doi:10.7155/jgaa.00591
apa: Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2022). On compatible matchings. Journal of Graph
Algorithms and Applications. Brown University. https://doi.org/10.7155/jgaa.00591
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” Journal of Graph Algorithms and Applications. Brown University,
2022. https://doi.org/10.7155/jgaa.00591.
ieee: O. Aichholzer et al., “On compatible matchings,” Journal of Graph
Algorithms and Applications, vol. 26, no. 2. Brown University, pp. 225–240,
2022.
ista: Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2022. On compatible matchings. Journal of Graph Algorithms and
Applications. 26(2), 225–240.
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” Journal of Graph Algorithms
and Applications, vol. 26, no. 2, Brown University, 2022, pp. 225–40, doi:10.7155/jgaa.00591.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, Journal of Graph Algorithms and Applications 26 (2022)
225–240.
date_created: 2022-08-21T22:01:56Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-02-23T13:54:21Z
day: '01'
ddc:
- '000'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.7155/jgaa.00591
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
file:
- access_level: open_access
checksum: dc6e255e3558faff924fd9e370886c11
content_type: application/pdf
creator: dernst
date_created: 2022-08-22T06:42:42Z
date_updated: 2022-08-22T06:42:42Z
file_id: '11940'
file_name: 2022_JourGraphAlgorithmsApplic_Aichholzer.pdf
file_size: 694538
relation: main_file
success: 1
file_date_updated: 2022-08-22T06:42:42Z
has_accepted_license: '1'
intvolume: ' 26'
issue: '2'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 225-240
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: Journal of Graph Algorithms and Applications
publication_identifier:
issn:
- 1526-1719
publication_status: published
publisher: Brown University
quality_controlled: '1'
related_material:
record:
- id: '9296'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 26
year: '2022'
...
---
_id: '9295'
abstract:
- lang: eng
text: "Hill's Conjecture states that the crossing number cr(\U0001D43E\U0001D45B)
\ of the complete graph \U0001D43E\U0001D45B in the plane (equivalently, the
sphere) is 14⌊\U0001D45B2⌋⌊\U0001D45B−12⌋⌊\U0001D45B−22⌋⌊\U0001D45B−32⌋=\U0001D45B4/64+\U0001D442(\U0001D45B3)
. Moon proved that the expected number of crossings in a spherical drawing in
which the points are randomly distributed and joined by geodesics is precisely
\ \U0001D45B4/64+\U0001D442(\U0001D45B3) , thus matching asymptotically the conjectured
value of cr(\U0001D43E\U0001D45B) . Let cr\U0001D443(\U0001D43A) denote the
crossing number of a graph \U0001D43A in the projective plane. Recently, Elkies
proved that the expected number of crossings in a naturally defined random projective
plane drawing of \U0001D43E\U0001D45B is (\U0001D45B4/8\U0001D70B2)+\U0001D442(\U0001D45B3)
. In analogy with the relation of Moon's result to Hill's conjecture, Elkies asked
if lim\U0001D45B→∞ cr\U0001D443(\U0001D43E\U0001D45B)/\U0001D45B4=1/8\U0001D70B2
. We construct drawings of \U0001D43E\U0001D45B in the projective plane that
disprove this."
acknowledgement: "We thank two reviewers for their corrections and suggestions on
the original version of this\r\npaper. This project has received funding from NSERC
Grant 50503-10940-500 and from the European Union’s Horizon 2020 research and innovation
programme under the Marie SkłodowskaCurie grant agreement No 754411, IST, Klosterneuburg,
Austria."
article_processing_charge: No
article_type: original
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: Dan
full_name: Mcquillan, Dan
last_name: Mcquillan
- first_name: R. Bruce
full_name: Richter, R. Bruce
last_name: Richter
- first_name: Gelasio
full_name: Salazar, Gelasio
last_name: Salazar
- first_name: Matthew
full_name: Sullivan, Matthew
last_name: Sullivan
citation:
ama: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 2021;97(3):426-440.
doi:10.1002/jgt.22665
apa: Arroyo Guevara, A. M., Mcquillan, D., Richter, R. B., Salazar, G., & Sullivan,
M. (2021). Drawings of complete graphs in the projective plane. Journal of
Graph Theory. Wiley. https://doi.org/10.1002/jgt.22665
chicago: Arroyo Guevara, Alan M, Dan Mcquillan, R. Bruce Richter, Gelasio Salazar,
and Matthew Sullivan. “Drawings of Complete Graphs in the Projective Plane.” Journal
of Graph Theory. Wiley, 2021. https://doi.org/10.1002/jgt.22665.
ieee: A. M. Arroyo Guevara, D. Mcquillan, R. B. Richter, G. Salazar, and M. Sullivan,
“Drawings of complete graphs in the projective plane,” Journal of Graph Theory,
vol. 97, no. 3. Wiley, pp. 426–440, 2021.
ista: Arroyo Guevara AM, Mcquillan D, Richter RB, Salazar G, Sullivan M. 2021. Drawings
of complete graphs in the projective plane. Journal of Graph Theory. 97(3), 426–440.
mla: Arroyo Guevara, Alan M., et al. “Drawings of Complete Graphs in the Projective
Plane.” Journal of Graph Theory, vol. 97, no. 3, Wiley, 2021, pp. 426–40,
doi:10.1002/jgt.22665.
short: A.M. Arroyo Guevara, D. Mcquillan, R.B. Richter, G. Salazar, M. Sullivan,
Journal of Graph Theory 97 (2021) 426–440.
date_created: 2021-03-28T22:01:41Z
date_published: 2021-03-23T00:00:00Z
date_updated: 2023-08-07T14:26:15Z
day: '23'
department:
- _id: UlWa
doi: 10.1002/jgt.22665
ec_funded: 1
external_id:
arxiv:
- '2002.02287'
isi:
- '000631693200001'
intvolume: ' 97'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2002.02287
month: '03'
oa: 1
oa_version: Preprint
page: 426-440
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Journal of Graph Theory
publication_identifier:
eissn:
- 1097-0118
issn:
- 0364-9024
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Drawings of complete graphs in the projective plane
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 97
year: '2021'
...
---
_id: '9296'
abstract:
- lang: eng
text: ' matching is compatible to two or more labeled point sets of size n with
labels {1,…,n} if its straight-line drawing on each of these point sets is
crossing-free. We study the maximum number of edges in a matching compatible to
two or more labeled point sets in general position in the plane. We show that
for any two labeled convex sets of n points there exists a compatible matching
with ⌊2n−−√⌋ edges. More generally, for any ℓ labeled point sets we construct
compatible matchings of size Ω(n1/ℓ) . As a corresponding upper bound, we use
probabilistic arguments to show that for any ℓ given sets of n points there
exists a labeling of each set such that the largest compatible matching has O(n2/(ℓ+1)) edges.
Finally, we show that Θ(logn) copies of any set of n points are necessary and
sufficient for the existence of a labeling such that any compatible matching consists
only of a single edge.'
acknowledgement: 'A.A. funded by the Marie Skłodowska-Curie grant agreement No. 754411.
Z.M. partially funded by Wittgenstein Prize, Austrian Science Fund (FWF), grant
no. Z 342-N31. I.P., D.P., and B.V. partially supported by FWF within the collaborative
DACH project Arrangements and Drawings as FWF project I 3340-N35. A.P. supported
by a Schrödinger fellowship of the FWF: J-3847-N35. J.T. partially supported by
ERC Start grant no. (279307: Graph Games), FWF grant no. P23499-N23 and S11407-N23
(RiSE).'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Oswin
full_name: Aichholzer, Oswin
last_name: Aichholzer
- 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: Zuzana
full_name: Masárová, Zuzana
id: 45CFE238-F248-11E8-B48F-1D18A9856A87
last_name: Masárová
orcid: 0000-0002-6660-1322
- first_name: Irene
full_name: Parada, Irene
last_name: Parada
- first_name: Daniel
full_name: Perz, Daniel
last_name: Perz
- first_name: Alexander
full_name: Pilz, Alexander
last_name: Pilz
- first_name: Josef
full_name: Tkadlec, Josef
id: 3F24CCC8-F248-11E8-B48F-1D18A9856A87
last_name: Tkadlec
orcid: 0000-0002-1097-9684
- first_name: Birgit
full_name: Vogtenhuber, Birgit
last_name: Vogtenhuber
citation:
ama: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, et al. On compatible matchings.
In: 15th International Conference on Algorithms and Computation. Vol 12635.
Springer Nature; 2021:221-233. doi:10.1007/978-3-030-68211-8_18'
apa: 'Aichholzer, O., Arroyo Guevara, A. M., Masárová, Z., Parada, I., Perz, D.,
Pilz, A., … Vogtenhuber, B. (2021). On compatible matchings. In 15th International
Conference on Algorithms and Computation (Vol. 12635, pp. 221–233). Yangon,
Myanmar: Springer Nature. https://doi.org/10.1007/978-3-030-68211-8_18'
chicago: Aichholzer, Oswin, Alan M Arroyo Guevara, Zuzana Masárová, Irene Parada,
Daniel Perz, Alexander Pilz, Josef Tkadlec, and Birgit Vogtenhuber. “On Compatible
Matchings.” In 15th International Conference on Algorithms and Computation,
12635:221–33. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-68211-8_18.
ieee: O. Aichholzer et al., “On compatible matchings,” in 15th International
Conference on Algorithms and Computation, Yangon, Myanmar, 2021, vol. 12635,
pp. 221–233.
ista: 'Aichholzer O, Arroyo Guevara AM, Masárová Z, Parada I, Perz D, Pilz A, Tkadlec
J, Vogtenhuber B. 2021. On compatible matchings. 15th International Conference
on Algorithms and Computation. WALCOM: Algorithms and Computation, LNCS, vol.
12635, 221–233.'
mla: Aichholzer, Oswin, et al. “On Compatible Matchings.” 15th International
Conference on Algorithms and Computation, vol. 12635, Springer Nature, 2021,
pp. 221–33, doi:10.1007/978-3-030-68211-8_18.
short: O. Aichholzer, A.M. Arroyo Guevara, Z. Masárová, I. Parada, D. Perz, A. Pilz,
J. Tkadlec, B. Vogtenhuber, in:, 15th International Conference on Algorithms and
Computation, Springer Nature, 2021, pp. 221–233.
conference:
end_date: 2021-03-02
location: Yangon, Myanmar
name: 'WALCOM: Algorithms and Computation'
start_date: 2021-02-28
date_created: 2021-03-28T22:01:41Z
date_published: 2021-02-16T00:00:00Z
date_updated: 2023-02-21T16:33:44Z
day: '16'
department:
- _id: UlWa
- _id: HeEd
- _id: KrCh
doi: 10.1007/978-3-030-68211-8_18
ec_funded: 1
external_id:
arxiv:
- '2101.03928'
intvolume: ' 12635'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2101.03928
month: '02'
oa: 1
oa_version: Preprint
page: 221-233
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: The Wittgenstein Prize
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '279307'
name: 'Quantitative Graph Games: Theory and Applications'
- _id: 2584A770-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: P 23499-N23
name: Modern Graph Algorithmic Techniques in Formal Verification
- _id: 25863FF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: S11407
name: Game Theory
publication: 15th International Conference on Algorithms and Computation
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030682101'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '11938'
relation: later_version
status: public
scopus_import: '1'
status: public
title: On compatible matchings
type: conference
user_id: D865714E-FA4E-11E9-B85B-F5C5E5697425
volume: 12635
year: '2021'
...
---
_id: '9468'
abstract:
- lang: eng
text: "Motivated by the successful application of geometry to proving the Harary--Hill
conjecture for “pseudolinear” drawings of $K_n$, we introduce “pseudospherical”
drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit
sphere $\\mathbb{S}^2$ in which the vertices of $G$ are represented as points---no
three on a great circle---and the edges of $G$ are shortest-arcs in $\\mathbb{S}^2$
connecting pairs of vertices. Such a drawing has three properties: (1) every edge
$e$ is contained in a simple closed curve $\\gamma_e$ such that the only vertices
in $\\gamma_e$ are the ends of $e$; (2) if $e\\ne f$, then $\\gamma_e\\cap\\gamma_f$
has precisely two crossings; and (3) if $e\\ne f$, then $e$ intersects $\\gamma_f$
at most once, in either a crossing or an end of $e$. We use properties (1)--(3)
to define a pseudospherical drawing of $G$. Our main result is that for the complete
graph, properties (1)--(3) are equivalent to the same three properties but with
“precisely two crossings” in (2) replaced by “at most two crossings.” The proof
requires a result in the geometric transversal theory of arrangements of pseudocircles.
This is proved using the surprising result that the absence of special arcs (coherent
spirals) in an arrangement of simple closed curves characterizes the fact that
any two curves in the arrangement have at most two crossings. Our studies provide
the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension
to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to
an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles
crossing twice.\r\n"
article_processing_charge: No
article_type: original
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: R. Bruce
full_name: Richter, R. Bruce
last_name: Richter
- first_name: Matthew
full_name: Sunohara, Matthew
last_name: Sunohara
citation:
ama: Arroyo Guevara AM, Richter RB, Sunohara M. Extending drawings of complete graphs
into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics.
2021;35(2):1050-1076. doi:10.1137/20M1313234
apa: Arroyo Guevara, A. M., Richter, R. B., & Sunohara, M. (2021). Extending
drawings of complete graphs into arrangements of pseudocircles. SIAM Journal
on Discrete Mathematics. Society for Industrial and Applied Mathematics. https://doi.org/10.1137/20M1313234
chicago: Arroyo Guevara, Alan M, R. Bruce Richter, and Matthew Sunohara. “Extending
Drawings of Complete Graphs into Arrangements of Pseudocircles.” SIAM Journal
on Discrete Mathematics. Society for Industrial and Applied Mathematics, 2021.
https://doi.org/10.1137/20M1313234.
ieee: A. M. Arroyo Guevara, R. B. Richter, and M. Sunohara, “Extending drawings
of complete graphs into arrangements of pseudocircles,” SIAM Journal on Discrete
Mathematics, vol. 35, no. 2. Society for Industrial and Applied Mathematics,
pp. 1050–1076, 2021.
ista: Arroyo Guevara AM, Richter RB, Sunohara M. 2021. Extending drawings of complete
graphs into arrangements of pseudocircles. SIAM Journal on Discrete Mathematics.
35(2), 1050–1076.
mla: Arroyo Guevara, Alan M., et al. “Extending Drawings of Complete Graphs into
Arrangements of Pseudocircles.” SIAM Journal on Discrete Mathematics, vol.
35, no. 2, Society for Industrial and Applied Mathematics, 2021, pp. 1050–76,
doi:10.1137/20M1313234.
short: A.M. Arroyo Guevara, R.B. Richter, M. Sunohara, SIAM Journal on Discrete
Mathematics 35 (2021) 1050–1076.
date_created: 2021-06-06T22:01:30Z
date_published: 2021-05-20T00:00:00Z
date_updated: 2023-08-08T13:58:12Z
day: '20'
department:
- _id: UlWa
doi: 10.1137/20M1313234
ec_funded: 1
external_id:
arxiv:
- '2001.06053'
isi:
- '000674142200022'
intvolume: ' 35'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2001.06053
month: '05'
oa: 1
oa_version: Preprint
page: 1050-1076
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: SIAM Journal on Discrete Mathematics
publication_identifier:
issn:
- '08954801'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of complete graphs into arrangements of pseudocircles
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 35
year: '2021'
...
---
_id: '7994'
abstract:
- lang: eng
text: In the recent study of crossing numbers, drawings of graphs that can be extended
to an arrangement of pseudolines (pseudolinear drawings) have played an important
role as they are a natural combinatorial extension of rectilinear (or straight-line)
drawings. A characterization of the pseudolinear drawings of K_n was found recently.
We extend this characterization to all graphs, by describing the set of minimal
forbidden subdrawings for pseudolinear drawings. Our characterization also leads
to a polynomial-time algorithm to recognize pseudolinear drawings and construct
the pseudolines when it is possible.
alternative_title:
- LIPIcs
article_number: 9:1 - 9:14
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: Julien
full_name: Bensmail, Julien
last_name: Bensmail
- first_name: R.
full_name: Bruce Richter, R.
last_name: Bruce Richter
citation:
ama: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. Extending drawings of graphs
to arrangements of pseudolines. In: 36th International Symposium on Computational
Geometry. Vol 164. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020.
doi:10.4230/LIPIcs.SoCG.2020.9'
apa: 'Arroyo Guevara, A. M., Bensmail, J., & Bruce Richter, R. (2020). Extending
drawings of graphs to arrangements of pseudolines. In 36th International Symposium
on Computational Geometry (Vol. 164). Zürich, Switzerland: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.SoCG.2020.9'
chicago: Arroyo Guevara, Alan M, Julien Bensmail, and R. Bruce Richter. “Extending
Drawings of Graphs to Arrangements of Pseudolines.” In 36th International Symposium
on Computational Geometry, Vol. 164. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2020. https://doi.org/10.4230/LIPIcs.SoCG.2020.9.
ieee: A. M. Arroyo Guevara, J. Bensmail, and R. Bruce Richter, “Extending drawings
of graphs to arrangements of pseudolines,” in 36th International Symposium
on Computational Geometry, Zürich, Switzerland, 2020, vol. 164.
ista: 'Arroyo Guevara AM, Bensmail J, Bruce Richter R. 2020. Extending drawings
of graphs to arrangements of pseudolines. 36th International Symposium on Computational
Geometry. SoCG: Symposium on Computational Geometry, LIPIcs, vol. 164, 9:1-9:14.'
mla: Arroyo Guevara, Alan M., et al. “Extending Drawings of Graphs to Arrangements
of Pseudolines.” 36th International Symposium on Computational Geometry,
vol. 164, 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, doi:10.4230/LIPIcs.SoCG.2020.9.
short: A.M. Arroyo Guevara, J. Bensmail, R. Bruce Richter, in:, 36th International
Symposium on Computational Geometry, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2020.
conference:
end_date: 2020-06-26
location: Zürich, Switzerland
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2020-06-22
date_created: 2020-06-22T09:14:21Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-02-23T13:22:12Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.4230/LIPIcs.SoCG.2020.9
ec_funded: 1
external_id:
arxiv:
- '1804.09317'
file:
- access_level: open_access
checksum: 93571b76cf97d5b7c8aabaeaa694dd7e
content_type: application/pdf
creator: dernst
date_created: 2020-06-23T11:06:23Z
date_updated: 2020-07-14T12:48:06Z
file_id: '8006'
file_name: 2020_LIPIcsSoCG_Arroyo.pdf
file_size: 592661
relation: main_file
file_date_updated: 2020-07-14T12:48:06Z
has_accepted_license: '1'
intvolume: ' 164'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 36th International Symposium on Computational Geometry
publication_identifier:
isbn:
- '9783959771436'
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extending drawings of graphs to arrangements of pseudolines
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 164
year: '2020'
...
---
_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: Graph-Theoretic Concepts
in Computer Science. Vol 12301. Springer Nature; 2020:325-338. doi:10.1007/978-3-030-60440-0_26'
apa: 'Arroyo Guevara, A. M., Klute, F., Parada, I., Seidel, R., Vogtenhuber, B.,
& Wiedera, T. (2020). Inserting one edge into a simple drawing is hard. In
Graph-Theoretic Concepts in Computer Science (Vol. 12301, pp. 325–338).
Leeds, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-60440-0_26'
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 Graph-Theoretic Concepts in Computer Science, 12301:325–38. Springer
Nature, 2020. https://doi.org/10.1007/978-3-030-60440-0_26.
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 Graph-Theoretic
Concepts in Computer Science, 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.” Graph-Theoretic Concepts in Computer Science, vol. 12301, Springer
Nature, 2020, pp. 325–38, doi:10.1007/978-3-030-60440-0_26.
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'
...
---
_id: '6638'
abstract:
- lang: eng
text: 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.
article_processing_charge: No
arxiv: 1
author:
- first_name: 'André '
full_name: 'Silva, André '
last_name: Silva
- 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: Bruce
full_name: Richter, Bruce
last_name: Richter
- first_name: Orlando
full_name: Lee, Orlando
last_name: Lee
citation:
ama: Silva A, Arroyo Guevara AM, Richter B, Lee O. Graphs with at most one crossing.
Discrete Mathematics. 2019;342(11):3201-3207. doi:10.1016/j.disc.2019.06.031
apa: Silva, A., Arroyo Guevara, A. M., Richter, B., & Lee, O. (2019). Graphs
with at most one crossing. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2019.06.031
chicago: Silva, André , Alan M Arroyo Guevara, Bruce Richter, and Orlando Lee. “Graphs
with at Most One Crossing.” Discrete Mathematics. Elsevier, 2019. https://doi.org/10.1016/j.disc.2019.06.031.
ieee: A. Silva, A. M. Arroyo Guevara, B. Richter, and O. Lee, “Graphs with at most
one crossing,” Discrete Mathematics, vol. 342, no. 11. Elsevier, pp. 3201–3207,
2019.
ista: Silva A, Arroyo Guevara AM, Richter B, Lee O. 2019. Graphs with at most one
crossing. Discrete Mathematics. 342(11), 3201–3207.
mla: Silva, André, et al. “Graphs with at Most One Crossing.” Discrete Mathematics,
vol. 342, no. 11, Elsevier, 2019, pp. 3201–07, doi:10.1016/j.disc.2019.06.031.
short: A. Silva, A.M. Arroyo Guevara, B. Richter, O. Lee, Discrete Mathematics 342
(2019) 3201–3207.
date_created: 2019-07-14T21:59:20Z
date_published: 2019-11-01T00:00:00Z
date_updated: 2023-08-29T06:31:41Z
day: '01'
department:
- _id: UlWa
doi: 10.1016/j.disc.2019.06.031
ec_funded: 1
external_id:
arxiv:
- '1901.09955'
isi:
- '000486358100025'
intvolume: ' 342'
isi: 1
issue: '11'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1901.09955
month: '11'
oa: 1
oa_version: Preprint
page: 3201-3207
project:
- _id: 26366136-B435-11E9-9278-68D0E5697425
name: Reglas de Conectividad funcional en el hipocampo
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Graphs with at most one crossing
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 342
year: '2019'
...
---
_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: 27th
International Symposium on Graph Drawing and Network Visualization. Vol 11904.
Springer Nature; 2019:230-243. doi:10.1007/978-3-030-35802-0_18'
apa: 'Arroyo Guevara, A. M., Derka, M., & Parada, I. (2019). Extending simple
drawings. In 27th International Symposium on Graph Drawing and Network Visualization
(Vol. 11904, pp. 230–243). Prague, Czech Republic: Springer Nature. https://doi.org/10.1007/978-3-030-35802-0_18'
chicago: Arroyo Guevara, Alan M, Martin Derka, and Irene Parada. “Extending Simple
Drawings.” In 27th International Symposium on Graph Drawing and Network Visualization,
11904:230–43. Springer Nature, 2019. https://doi.org/10.1007/978-3-030-35802-0_18.
ieee: A. M. Arroyo Guevara, M. Derka, and I. Parada, “Extending simple drawings,”
in 27th International Symposium on Graph Drawing and Network Visualization,
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.” 27th International
Symposium on Graph Drawing and Network Visualization, vol. 11904, Springer
Nature, 2019, pp. 230–43, doi:10.1007/978-3-030-35802-0_18.
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'
...