You can manage bookmarks using lists, please log in to your user account for this.
Media type:
Report;
E-Book;
Electronic Conference Proceeding
Title:
Extending drawings of graphs to arrangements of pseudolines ; LIPIcs
Contributor:
Arroyo Guevara, Alan M
[Author];
Bensmail, Julien
[Author];
Bruce Richter, R.
[Author]
imprint:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020
Published in: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
Language:
English
DOI:
https://doi.org/10.4230/LIPIcs.SoCG.2020.9
ISBN:
9783959771436
Origination:
Footnote:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Description:
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.