DROPS

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}
}

Search Results

Documents authored by Arroyo, Alan

Extending Drawings of Graphs to Arrangements of Pseudolines

Abstract

Cite as

Thanks for your feedback!

Could not send message