---
_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: '312'
abstract:
- lang: eng
text: Motivated by biological questions, we study configurations of equal spheres
that neither pack nor cover. Placing their centers on a lattice, we define the
soft density of the configuration by penalizing multiple overlaps. Considering
the 1-parameter family of diagonally distorted 3-dimensional integer lattices,
we show that the soft density is maximized at the FCC lattice.
acknowledgement: This work was partially supported by the DFG Collaborative Research
Center TRR 109, “Discretization in Geometry and Dynamics,” through grant I02979-N35
of the Austrian Science Fund (FWF).
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Mabel
full_name: Iglesias Ham, Mabel
id: 41B58C0C-F248-11E8-B48F-1D18A9856A87
last_name: Iglesias Ham
citation:
ama: Edelsbrunner H, Iglesias Ham M. On the optimality of the FCC lattice for soft
sphere packing. SIAM J Discrete Math. 2018;32(1):750-782. doi:10.1137/16M1097201
apa: Edelsbrunner, H., & Iglesias Ham, M. (2018). On the optimality of the FCC
lattice for soft sphere packing. SIAM J Discrete Math. Society for Industrial
and Applied Mathematics . https://doi.org/10.1137/16M1097201
chicago: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the
FCC Lattice for Soft Sphere Packing.” SIAM J Discrete Math. Society for
Industrial and Applied Mathematics , 2018. https://doi.org/10.1137/16M1097201.
ieee: H. Edelsbrunner and M. Iglesias Ham, “On the optimality of the FCC lattice
for soft sphere packing,” SIAM J Discrete Math, vol. 32, no. 1. Society
for Industrial and Applied Mathematics , pp. 750–782, 2018.
ista: Edelsbrunner H, Iglesias Ham M. 2018. On the optimality of the FCC lattice
for soft sphere packing. SIAM J Discrete Math. 32(1), 750–782.
mla: Edelsbrunner, Herbert, and Mabel Iglesias Ham. “On the Optimality of the FCC
Lattice for Soft Sphere Packing.” SIAM J Discrete Math, vol. 32, no. 1,
Society for Industrial and Applied Mathematics , 2018, pp. 750–82, doi:10.1137/16M1097201.
short: H. Edelsbrunner, M. Iglesias Ham, SIAM J Discrete Math 32 (2018) 750–782.
date_created: 2018-12-11T11:45:46Z
date_published: 2018-03-29T00:00:00Z
date_updated: 2023-09-13T09:34:38Z
day: '29'
department:
- _id: HeEd
doi: 10.1137/16M1097201
external_id:
isi:
- '000428958900038'
intvolume: ' 32'
isi: 1
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://pdfs.semanticscholar.org/d2d5/6da00fbc674e6a8b1bb9d857167e54200dc6.pdf
month: '03'
oa: 1
oa_version: Submitted Version
page: 750 - 782
project:
- _id: 2561EBF4-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: I02979-N35
name: Persistence and stability of geometric complexes
publication: SIAM J Discrete Math
publication_identifier:
issn:
- '08954801'
publication_status: published
publisher: 'Society for Industrial and Applied Mathematics '
publist_id: '7553'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the optimality of the FCC lattice for soft sphere packing
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 32
year: '2018'
...