We prove that every set of Δ- 1 slopes is 1-bend universal for the planar graphs with maximum vertex degree Δ. This means that any planar graph with maximum degree Δ admits a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges can be chosen in any given set of Δ- 1 slopes. Our result improves over previous literature in three ways: Firstly, it improves the known upper bound of 32(Δ-1) on the 1-bend planar slope number; secondly, the previously known algorithms compute 1-bend planar drawings by using sets of O(Δ) slopes that may vary depending on the input graph; thirdly, while these algorithms typically minimize the slopes at the expenses of constructing drawings with poor angular resolution, we can compute drawings whose angular resolution is at least πΔ-1, which is worst-case optimal up to a factor of 34. Our proofs are constructive and give rise to a linear-time drawing algorithm.

Universal Slope Sets for 1-Bend Planar Drawings

Liotta, Giuseppe;Montecchiani, Fabrizio
2019

Abstract

We prove that every set of Δ- 1 slopes is 1-bend universal for the planar graphs with maximum vertex degree Δ. This means that any planar graph with maximum degree Δ admits a planar drawing with at most one bend per edge and such that the slopes of the segments forming the edges can be chosen in any given set of Δ- 1 slopes. Our result improves over previous literature in three ways: Firstly, it improves the known upper bound of 32(Δ-1) on the 1-bend planar slope number; secondly, the previously known algorithms compute 1-bend planar drawings by using sets of O(Δ) slopes that may vary depending on the input graph; thirdly, while these algorithms typically minimize the slopes at the expenses of constructing drawings with poor angular resolution, we can compute drawings whose angular resolution is at least πΔ-1, which is worst-case optimal up to a factor of 34. Our proofs are constructive and give rise to a linear-time drawing algorithm.
2019
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11391/1448705
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 8
  • ???jsp.display-item.citation.isi??? 6
social impact