Crossing Numbers of Beyond-Planar Graphs
| Autor: | Pavel Valtr, Markus Chimani, Philipp Kindermann, Fabrizio Montecchiani |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Beyond planarity
Computational Geometry (cs.CG) FOS: Computer and information sciences 050101 languages & linguistics General Computer Science Discrete Mathematics (cs.DM) 05 social sciences 02 engineering and technology Computer Science::Computational Geometry Crossing numbers Theoretical Computer Science Planar graph Combinatorics symbols.namesake 0202 electrical engineering electronic engineering information engineering symbols Computer Science - Computational Geometry 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Crossing number (graph theory) Edge crossing Computer Science - Discrete Mathematics 1-planar graphs Mathematics |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030358013 Graph Drawing |
| DOI: | 10.1007/978-3-030-35802-0_6 |
| Popis: | We study the 1-planar, quasi-planar, and fan-planar crossing number in comparison to the (unrestricted) crossing number of graphs. We prove that there are $n$-vertex 1-planar (quasi-planar, fan-planar) graphs such that any 1-planar (quasi-planar, fan-planar) drawing has $\Omega(n)$ crossings, while $O(1)$ crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns. Comment: Appears in the Proceedings of the 27th International Symposium on Graph Drawing and Network Visualization (GD 2019) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|