1 Search Results for "Arroyo, Alan"

Document
DOI: 10.4230/LIPIcs.SoCG.2020.9
Extending Drawings of Graphs to Arrangements of Pseudolines

Authors: Alan Arroyo, Julien Bensmail, and R. Bruce Richter

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
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.
Cite as

Alan Arroyo, Julien Bensmail, and R. Bruce Richter. Extending Drawings of Graphs to Arrangements of Pseudolines. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{arroyo_et_al:LIPIcs.SoCG.2020.9,
  author =	{Arroyo, Alan and Bensmail, Julien and Richter, R. Bruce},
  title =	{{Extending Drawings of Graphs to Arrangements of Pseudolines}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{9:1--9:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.9},
  URN =		{urn:nbn:de:0030-drops-121672},
  doi =		{10.4230/LIPIcs.SoCG.2020.9},
  annote =	{Keywords: graphs, graph drawings, geometric graph drawings, arrangements of pseudolines, crossing numbers, stretchability}
}
  • Refine by Author
  • 1 Arroyo, Alan
  • 1 Bensmail, Julien
  • 1 Richter, R. Bruce

  • Refine by Classification

  • Refine by Keyword
  • 1 arrangements of pseudolines
  • 1 crossing numbers
  • 1 geometric graph drawings
  • 1 graph drawings
  • 1 graphs
  • Show More...

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2020

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact