Back to Search
Start Over
Extending Drawings of Graphs to Arrangements of Pseudolines
- Source :
- SoCG 2020-36th International Symposium on Computational Geometry, SoCG 2020-36th International Symposium on Computational Geometry, Jun 2020, Zürich, Switzerland, Journal of Computational Geometry, Journal of Computational Geometry, 2021, 12 (2), pp.3-24. ⟨10.20382/jocg.v12i2a2⟩, Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2021, 12 (2), pp.3-24. ⟨10.20382/jocg.v12i2a2⟩
- Publication Year :
- 2020
- Publisher :
- HAL CCSD, 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.<br />Journal of Computational Geometry, Vol. 12 No. 2 (2021)
- Subjects :
- graphs
050101 languages & linguistics
crossing numbers
05 social sciences
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
arrangements of pseudolines
FOS: Mathematics
0202 electrical engineering, electronic engineering, information engineering
Mathematics - Combinatorics
020201 artificial intelligence & image processing
0501 psychology and cognitive sciences
graph drawings
Combinatorics (math.CO)
stretchability
05C10, 05C85, 52C40, 52C30
geometric graph drawings
Subjects
Details
- Language :
- English
- ISSN :
- 1920180X
- Database :
- OpenAIRE
- Journal :
- SoCG 2020-36th International Symposium on Computational Geometry, SoCG 2020-36th International Symposium on Computational Geometry, Jun 2020, Zürich, Switzerland, Journal of Computational Geometry, Journal of Computational Geometry, 2021, 12 (2), pp.3-24. ⟨10.20382/jocg.v12i2a2⟩, Journal of Computational Geometry, Carleton University, Computational Geometry Laboratory, 2021, 12 (2), pp.3-24. ⟨10.20382/jocg.v12i2a2⟩
- Accession number :
- edsair.doi.dedup.....0b1b86382618d848faf7f93f02b185ed