A 1-planar drawing of a graph is such that each edge is crossed at most once. In 1997, Pach and Tóth showed that any 1-planar drawing with n vertices has at most 4n−8 edges and that this bound is tight for n 12. We show that, in fact, 1-planar drawings with n vertices have at most 4n−9 edges, if we require that the edges are straight-line segments. We also prove that this bound is tight for infinitely many values of n>=8. Furthermore, we investigate the density of 1-planar straight-line drawings with additional constraints on the vertex positions. We show that 1-planar drawings of bipartite graphs whose vertices lie on two distinct horizontal layers have at most 1.5n − 2 edges, and we prove that 1-planar drawings such that all vertices lie on a circumference have at most 2.5n − 4 edges; both these bounds are also tight.

Density of straight-line 1-planar graph drawings

DIDIMO, WALTER
2013

Abstract

A 1-planar drawing of a graph is such that each edge is crossed at most once. In 1997, Pach and Tóth showed that any 1-planar drawing with n vertices has at most 4n−8 edges and that this bound is tight for n 12. We show that, in fact, 1-planar drawings with n vertices have at most 4n−9 edges, if we require that the edges are straight-line segments. We also prove that this bound is tight for infinitely many values of n>=8. Furthermore, we investigate the density of 1-planar straight-line drawings with additional constraints on the vertex positions. We show that 1-planar drawings of bipartite graphs whose vertices lie on two distinct horizontal layers have at most 1.5n − 2 edges, and we prove that 1-planar drawings such that all vertices lie on a circumference have at most 2.5n − 4 edges; both these bounds are also tight.
2013
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/1078465
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 46
  • ???jsp.display-item.citation.isi??? 31
social impact