This paper studies optimal-area visibility representations of n-vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the outer face and each edge is crossed at most once. We show that any graph of this family admits an embedding-preserving visibility representation whose area is O(n1.5) and prove that this area bound is worst-case optimal. We also show that O(n1.48) area can be achieved if we represent the vertices as L-shaped orthogonal polygons or if we do not respect the embedding but still have at most one crossing per edge. We also extend the study to other representation models and, among other results, construct asymptotically optimal O(npw(G)) area bar-1-visibility representations, where pw(G) ∈ O(log n) is the pathwidth of the outer-1-planar graph G.

Optimal-Area Visibility Representations of Outer-1-Plane Graphs

Liotta G.;Montecchiani F.
2021

Abstract

This paper studies optimal-area visibility representations of n-vertex outer-1-plane graphs, i.e. graphs with a given embedding where all vertices are on the boundary of the outer face and each edge is crossed at most once. We show that any graph of this family admits an embedding-preserving visibility representation whose area is O(n1.5) and prove that this area bound is worst-case optimal. We also show that O(n1.48) area can be achieved if we represent the vertices as L-shaped orthogonal polygons or if we do not respect the embedding but still have at most one crossing per edge. We also extend the study to other representation models and, among other results, construct asymptotically optimal O(npw(G)) area bar-1-visibility representations, where pw(G) ∈ O(log n) is the pathwidth of the outer-1-planar graph G.
2021
978-3-030-92930-5
978-3-030-92931-2
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/1501322
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact