## Abstract

We introduce the family of k-gap-planar graphs for k ≥ 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 |
---|---|

Title of host publication | Graph Drawing and Network Visualization - 25th International Symposium, GD 2017, Revised Selected Papers |

Editors | F. Frati, K-L. Ma |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 531-545 |

Number of pages | 15 |

ISBN (Electronic) | 978-3-319-73915-1 |

ISBN (Print) | 9783319739144 |

DOIs | |

Publication status | Published - 1 Jan 2018 |

Event | 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) - Boston, United States Duration: 25 Sep 2017 → 27 Sep 2017 Conference number: 25 https://gd2017.ccis.northeastern.edu/ |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Volume | 10692 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 25th International Symposium on Graph Drawing and Network Visualization (GD 2017) |
---|---|

Abbreviated title | GD 2017 |

Country/Territory | United States |

City | Boston |

Period | 25/09/17 → 27/09/17 |

Internet address |