Abstract
We introduce the family of $k$-gap-planar graphs for $k \geq 0$, i.e., graphs that have a drawing in which each crossing is assigned to one of the two involved edges and each edge is assigned at most $k$ of its crossings. This definition finds motivation in edge casing, as a $k$-gap-planar graph can be drawn crossing-free after introducing at most $k$ local gaps per edge. We obtain results on the maximum density, drawability of complete graphs, complexity of the recognition problem, and relationships with other families of beyond-planar graphs.
Original language | English |
---|---|
Article number | 1708.07653 |
Number of pages | 23 |
Journal | arXiv |
Publication status | Published - 2017 |
Bibliographical note
Appears in the Proceedings of the 25th International Symposium on Graph Drawing and Network Visualization (GD 2017)Keywords
- cs.CG